0194. Divide et Impere

Input file name:	divide.in
Output file name:	divide.out
Time limit:	250 ms
Memory limit:	32 megabytes

There is a set of cells Q, which completely lies in a square of N*N cells. You are to divide Q into two subsets Q₁ and Q₂ in such way, that one could be transformed to another by applying parallel shiftings and rotatings per 90^o.

Input file

First line of the input contains single integer number N (1 ≤ N ≤ 20). Next N lines contains N characters each: `1', if the cell belongs to Q, and `0' in another case.

Output file

First line of output file must contain the word "YES", if Q could be divided and "NO" in another case. In the case of positive answer print one subset Q₁ or Q₂ in N lines, each of which contains N characters: `1', if cell belongs to your subset, and `0' in another case.

Examples:

divide.in	divide.out
3 100 011 010	YES 100 010 000
3 100 101 010	NO

Source: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Discuss       Submit a solution



Printable version