SPOJ in Gyumri

   Серёжа - очень любознательный мальчик. Вот сейчас он прознал про игру "жизнь". Место действия этой игры - это размеченная на клетки ограниченная поверхность. Каждая клетка на поверхности может находиться в двух состояниях: быть живой или быть мёртвой. Клетка имеет восемь соседей (кроме крайних, которые имеют меньше соседей). Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:

• пустая (мёртвая) клетка рядом с тремя живыми клетками-соседями оживает;
• если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить;
• в противном случае (если соседей меньше двух или больше трёх) клетка умирает (от одиночества или от перенаселённости).

   Серёжа придумал для себя интересное расположение живых клеток для первого поколения и хочет узнать, что произойдёт с ними через K шагов, то есть каковым будет (K+1)-е поколение.

Входные данные.

   N M K размеры поля. 1 ≤ N,M ≤ 100. K ≤ 20

   A₁₁A₁₂…A_1M

   A₂₁A₂₂…A_2M

   …

   A_N1A_N2…A_NM

   A_ij = 1, если клетка изначально жива, A_ij = 0, если клетка изначально мертва

Выходные данные.

   B₁₁B₁₂…B_1M      B_ij = 1, если клетка жива после K шагов

   B₂₁B₂₂…B_2M      B_ij = 0, если клетка мертва после K шагов

   …

   B_N1B_N2…B_NM

Пример.