В грядущем 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

Этот вывод соответствует следующей раскраске. Серые клетки обозначают окраску в красный цвет, а белые клетки — окраску в белый цвет. Штриховая и пунктирная линии являются осями симметрии красной и белой областей соответственно.

Следующие способы раскраски не удовлетворяют условиям: