0194. Divide et Impere

Имя входного файла:	divide.in
Имя выходного файла:	divide.out
Ограничение по времени:	250 ms
Ограничение по памяти:	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

Источник: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Обсудить       Отправить решение