2643. Ingredient

单点时限: 2.0 sec

内存限制: 256 MB

Adam C. Murphy loves drinking, thus he collected all kind of drinks in his apartment. One day he felt boring, so he tried to mix a brand new kind of drink out of the old ones. After searching around his collections, he found that he had N (N<=10) kind of drinks. Each drink is composed of N ingredients. You can refer to Sample Input for more details. What Adam C. Murphy wants to do was to create a kind of mixture, which all the N ingredients had a certain ratio.

All the content in N drinks is given in integer, for example, {20, 45, 10, 3, 3} indicates a kind of drink with 81 volume with 20,45,10,3,3 for each different ingredients. Adam C. Murphy cherish his drinks so much that he will use either one whole bottle or not a drop of it, and he wanted to make this mixture out with least numbers of bottles.

Now Adam C. Murphy asks you for help. He wants to do it with minimum quantities of drinks, or if it was impossible at all.

You may assume Adam C. Murphy’s drinks are unlimited in quantity, and each kind of drink is unique, i.e. any kind of drink can’t be mixed from other N-1 drinks.

输入格式

Input contains several test cases.

For each test case:

The first line is N (N<=10), represents the number of kinds.

The second line has N integer, which describes Adam C. Murphy’s ideal combination of ingredients.

Last N line, each line has N integer, which indicates each i-th (1<=i<=N) drink’s ingredients.

输出格式

For each test case, print one line, first N integer for the number of bottle to be used for each kind.

Finally, print one more integer S to show Adam C. Murphy how many bottles of the new ‘invention’ he can get.

If Adam can’t make his ideal mixture in any case, output a line ‘NONE’

Hint

During the process, 64-bit integer will be enough.

样例

Input
3
3 4 5
1 2 3
3 7 1
2 1 2
Output
8 1 5 7

1 人解决,3 人已尝试。

3 份提交通过,共有 11 份提交。

9.9 EMB 奖励。

创建: 15 年,2 月前.

修改: 7 年,1 月前.

最后提交: 12 年,11 月前.

来源: 多校联合比赛BNU站

题目标签