Террористы Аль-Каиды по своим каналам связи передавали план подземного бункера. Бункер, имеющий прямоугольную форму (по периметру прямоугольника - стены, также имеются внутренние стены, разделяющие помещения в бункере), может быть разбит на клетки в 1 кв.м. Известно, что схема бункера была закодирована следующим образом: каждой клетке сопоставлен код, определяющий наличие у нее стен. Этот код образован суммой чисел: 1 (клетка имеет стену на севере), 2 - на востоке, 4 - на юге, 8 - на западе.
После составления таблицы чисел к ней было применено шифрующее преобразование, а именно: в некотором порядке были переставлены строки матрицы и, затем, столбцы матрицы. Полученная таблица была передана и перехвачена.
Вам надо написать программу, восстанавливающую схему бункера. Если схема не может быть однозначно восстановлена, достаточно выдать один из вариантов.
Входные данные
Первая строка входного файла INPUT.TXT содержит числа М - высота и N - ширина прямоугольника в метрах (1 Ј M, N Ј 30). Последующие М строк содержат по N чисел, представляющих зашифрованную схему.
Выходные данные
В выходной файл OUTPUT.TXT вывести М строк по N чисел, представляющих расшифрованную схему. Для расшифрованной схемы восток - слева, запад - справа, север - сверху, юг - снизу.
| Пример INPUT.TXT: | OUTPUT.TXT для примера: |
| 2 2 | 11 11 |
| 6 12 | 12 6 |
| 11 11 |
Ограничение времени: 1 сек на тест