Республиканская олимпиада по информатике, 2011 год, 10-11 классы

Есеп B. Ферзьдер

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

$N \times N$ шахмат тақтасында сандар жазылған — әр ұяшықта бiр сан. $N$ ферздердi бiр-бiрiн ұрмайтындай (егер екi ферзь бiр вертикальда, горизонтальда немесе диагональда тұрса, олар бiр-бiрiн ұрады) және олар тұрған ұяшықтардағы сандардың қосындысы ең көп болатындай етiп қойыңыз.

Формат входного файла

Енгiзу файлының бiрiншi жолында бiр бүтiн сан $N$ берiледi $(1 \le N \le 15).$ Келесi $N$ жолдың әрқайсысында $N$ терiс емес, 1000-нан аспайтын бүтiн сандар — тақтаның сипаттамасы берiледi. Жолдағы сандар бос орынмен бөлiнген.

Формат выходного файла

Шығыс файлда әрқайсысында $N$ сандар болатындай $N$ жолдар шығарыңыз. $i$-шi жодағы $j$-шi сан 1-ге тең, егер $(i, j)$ ұяшығында ферзь тұрса, және 0-ге, егер тұрмаса.

Примеры:

Вход

4
1 2 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Ответ

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0