У прийдешньому 20XX році в Японії відбудеться Міжнародний фестиваль інформатики (International Omatsuri in Informatics). У межах підготовки до його проведення вам доручили створити логотип цього фестивалю.

Логотип Міжнародного фестивалю інформатики щоразу створюється на основі певного фіксованого малюнка. Цей малюнок складається з кількох клітинок, вибраних із прямокутної сітки квадратних клітинок завширшки $W$ клітинок по горизонталі та заввишки $H$ клітинок по вертикалі. Цього разу ви вирішили розфарбувати цей малюнок у кольори державного прапора Японії — червоний і білий, щоб зробити з нього логотип. Щоб не ускладнювати роботу з розфарбовування, для $1$ клітинки можна використати лише $1$ колір.

Щоб вирішити, як найкраще розподілити кольори, ви звернулися за порадою до знайомого дизайнера. Згідно з його чудовим естетичним смаком, бажаним є такий дизайн, у якому і область, зафарбована червоним, і область, зафарбована білим, утворюють фігури, що мають осьову симетрію. Крім того, з міркувань колірного балансу він також сказав, що кількість клітинок, зафарбованих червоним, краще зробити рівною $K$. Оскільки сам спосіб розфарбування, що задовольняє ці умови, він вам не повідомив, вам потрібно знайти його самостійно. За заданим малюнком та значенням $K$ напишіть програму, яка знаходить $1$ спосіб розфарбування, що задовольняє умови.

Вхідні дані

У $1$-му рядку через пробіл записано $3$ цілі числа $W, H, K$ ($1 \le W \le 40$, $1 \le H \le 40$, $1 \le K \le WH - 1$). Вони позначають ширину і висоту заданого малюнка, а також кількість клітинок, які потрібно пофарбувати в червоний колір.

Наступні $H$ рядків містять дані малюнка. У $i + 1$-му рядку ($1 \le i \le H$) через пробіл записано $W$ чисел, кожне з яких дорівнює $0$ або $1$. Якщо $j$-те ціле число ($1 \le j \le W$) у $i + 1$-му рядку дорівнює $1$, це означає, що клітинка в $i$-му рядку зверху і $j$-му стовпці зліва використовується в малюнку; якщо воно дорівнює $0$, то ця клітинка в малюнку не використовується. У малюнку обов'язково використовується щонайменше $2$ клітинки. Гарантується, що значення $K$ строго менше за кількість клітинок, що використовуються в малюнку.

Для будь-яких вхідних даних, що використовуються під час оцінювання, існує щонайменше $1$ спосіб розфарбування, який задовольняє умови.

Вихідні дані

Виведення необхідно здійснювати у стандартний потік виведення. Виведіть цілі числа, що задають розфарбування: по $W$ чисел через пробіл у кожному з $H$ рядків. Якщо $j$-те ціле число в $i$-му рядку дорівнює $1$, це означає, що клітинка в $i$-му рядку зверху і $j$-му стовпці зліва фарбується в червоний колір; якщо воно дорівнює $2$ — ця клітинка фарбується в білий колір. Для клітинок, які не використовуються в малюнку, виведіть $0$.

Якщо можливих способів розфарбування декілька, ви можете вивести будь-який із них.

Критерії оцінювання

Серед даних, що використовуються для оцінювання, для $20\%$ балів виконується $W, H \le 5$.

Приклад вводу 1

4 3 2
0 1 0 0
1 0 1 1
1 0 0 0

Приклад виводу 1

0 2 0 0
1 0 2 1
2 0 0 0

Це виведення відповідає такому способу розфарбування. Сірі клітинки позначають фарбування в червоний колір, а білі клітинки — фарбування в білий колір. Штрихова та пунктирна лінії є осями симетрії червоної та білої областей відповідно.

Наступні способи розфарбування не задовольняють умови: