21912_Ingredien

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'

3
3 4 5
1 2 3
3 7 1
2 1 2

8 1 5 7

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