Saturated macrophanes are extracted from their primitive forms - non-saturated macrophanes - in a long production process consisting of several stages. During each stage a macrophane saturation degree increases by 1, step by step from 0 to N, where N is a positive integer not greater than 144.

For every saturation degree n < N there exist several - from one to seven - concurrent paths of the production process, on which a macrophane saturation degree increases from n to n+1. On each of the paths a macrophane temperature changes by an integer value from -3 to 3 degrees centigrade. The changes on each path leading from a saturation degree n to n+1 are different. To increase saturation of a macrophane by one, any one of them is to be chosen.

A macrophane saturation process may run in different ways, because we may choose different paths between successive saturation degrees. However, one should know that a macrophane dies, if its temperature drops below 15°C or exceeds 34°C.

A cost of saturation of a macrophane is a sum of absolute values of all temperature changes it undergoes on successive paths of its saturation process.

We aim at minimizing that cost while planning a course of a macrophane saturation process. A macrophane must not die.

Example

Let us consider the case described by means of the following graph, where successive values of a saturation degree are written in squares, and temperature increments on corresponding paths are written by arrows:

There are eight different choices of bringing a non-saturated macrophane of starting temperature t₀ = 25°C to its full saturation degree 5.

In the less expensive run of this process the saturation cost is:

|1| + |0| + |3| + |3| + |-1| = 8,

|-3| + |-2| + |3| + |3| + |2| = 13.

If a macrophane has starting temperature t₀ = 33°C, then there exists only one choice of bringing it to full saturation, and its cost is:

|-3| + |-2| + |3| + |3| + |-1| = 12.

If a macrophane has starting temperature 34°C, then it is not possible to bring it alive to a saturation state.

Task

Write a program that from the text file MAK.IN reads a set of data on a process of extraction of saturated macrophanes, and next, successively for every admissible macrophane starting temperature from 15°C to 34°C, writes the following in separate lines of the file MAK.OUT:

• the word NIE ("no"), if a non-saturated macrophane of corresponding starting temperature cannot be brought alive to a saturation state, or
• a run of the saturation process having the minimal cost, in a form of a sequence of N numbers in the range of [-3, 3], denoting temperature changes on successive paths of this process, assuming that such a process is possible.

If for some starting temperature there are many runs of the macrophane saturation process having the minimal cost, your program should write only one of them.

A data set in the file MAK.IN consists of N <= 144 nonempty lines. For every saturation degree n in {0, 1, ..., N-1} the n-th line of the file contains at most seven integers from the range [-3, 3], in increasing order and separated by a space. The numbers denote corresponding temperature changes on all paths increasing a saturation degree of a macrophane from n to n+1. Immediately after the last number written in the N-th line there is the end of the file.

We assume that the data in the file is written faultlessly and the program needs not examine its correctness.

A set of results should be written to the file MAK.OUT in twenty consecutive lines. In each line the word NIE ("no") or a sequence of N integers from the range [-3, 3] separated by a space should be written. Immediately after the last number or the word NIE in the twentieth line there should be the end of the file.

Example

For the file MAK.IN:

-3 1
-2 0
3
3
-1 2(end of file)

1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 0 3 3 -1
1 -2 3 3 -1
1 -2 3 3 -1
-3 0 3 3 -1
-3 0 3 3 -1
-3 -2 3 3 -1
-3 -2 3 3 -1
NIE(end of file)

At the beginning of your program, in a comment, give your last and first name, and the number of your working stand.

Your program should look for the file MAK.IN in the current directory and create the file MAK.OUT also in the current directory. The source file containing the program written by you should be named MAK.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file MAK.EXE. Both the files should be stored on a hard disk and on a floppy disk.

The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk, and of the description of your algorithm and the justification of its correctness.