28. Игра

В свободное от занятий по программированию время Вася любит играть в самостоятельно придуманную им игру <<Жизнь>>.

Игра происходит на поле, состоящем из $n \times m$ одинаковых клеток. Для удобства Вася нумерует все строки поля целыми числами от $1$ до $n$ в порядке сверху-вниз, а также нумерует все столбцы поля целыми числами от $1$ до $m$ в порядке слева-направо.

Вася считает соседними те клетки поля, которые имеют общее ребро.

Процесс игры состоит из $k$ итераций. На каждой итерации игры каждая клетка поля находится в одном из трех состояний:

1. Неактивна. На поле Вася помечает такую клетку цифрой $1$.
2. Стабильна. На поле Вася помечает такую клетку цифрой $2$.
3. Нестабильна. На поле Вася помечает такую клетку цифрой $3$.

Активными Вася называет те клетки поля, которые находятся в стабильном или нестабильном состояниях.

Вася начинает игру с поля, каждая клетка которого находится в некотором заранее выбранном им состоянии.

При переходе к следующей итерации игры Вася формирует новое поле, состояние каждой клетки в котором назначается по следующим правилам:

1. Если у клетки на предыдущей итерации была более, чем одна соседняя клетка в стабильном состоянии, то на следующей итерации клетка будет находиться в стабильном состоянии.
2. Если не выполняется первое правило и у клетки на предыдущей итерации был хотя бы один сосед в активном состоянии, то на следующей итерации клетка будет находиться в нестабильном состоянии.
3. Если не выполняются предыдущие правила, то на следующей итерации клетка будет находиться в неактивном состоянии.

Вася хочет заранее спланировать для каждой клетки, сколько изменений состояния ему придется сделать за весь ход игры. Так как Вася ещё не успел разобраться во всех тонкостях программирования, он просит Вас помочь ему в этой задаче.

В первой строке входных данных записано три целых числа — $n$, $m$, $k$ ($1 \leq n, m, k \leq 100$).

В последующих $n$ строках записано состояние каждой клетки исходно выбранного Васей поля. В $i$-й ($1 \leq i \leq n$) из этих строк записано $m$ чисел — $a_{i1}, \dots, a_{im}$, где $a_{ij} \in \{1, 2, 3\}$ — состояние клетки в строке с номером $i$ и столбце с номером $j$ исходно выбранного Васей поля.

Все числа в каждой строке разделены ровно одним пробелом.

В $i$-й ($1 \leq i \leq n$) строке выходных данных Вам необходимо вывести $m$ целых чисел — $b_{i1}, \dots, b_{im}$, где $b_{ij}$ — количество изменений состояния клетки в строке с номером $i$ и столбце с номером $j$.

В первом примере на каждой итерации клетка в неактивном состоянии (1) получает нестабильное состояние (3), а каждая клетка в нестабильном состоянии (3) получает неактивное состояние (1).

Во втором и третьем примерах после первой итерации все клетки получают нестабильное состояние (3) и больше не меняют свое состояние.