题目描述

生命游戏(Game of life)由英国数学家John Conway在1970年发明。事实上，它是一个“零人游戏”，也没有胜负之分，而是相当于一个确定性自动机。游戏在$\red{N×M}$的细胞组成的矩阵里进行，每个细胞每个时刻的状态可能是“存活”或者“休眠”两种,细胞矩阵的状态会按以下规则进行演化： 一个存活状态的细胞，在某一秒，若周围的存活状态的细胞数目不足两个，则下一秒将由于孤独而进入休眠状态。一个存活状态的细胞，在某一秒，若周围的存活状态的细胞数目超过三个，则下一秒将由于过度拥挤而进入休眠状态。一个存活状态的细胞，在某一秒，若周围的存活状态的细胞数目为两或三个，则下一秒将继续保持存活状态。一个休眠状态的细胞，在某一秒，若周围的存活状态的细胞数目为正好三个，则认为是比较适合生存的状态，将于 下一秒进入存活状态。这里“周围”的范围包括一个细胞的上、下、左、右、左上、左下、右上、右下的细胞，如果存在的话。现在，给定一个初始状态（即第$\red{1}$秒时的状态），请按照规则计算第T秒时的状态。

输入格式

第一行，三个空格隔开的整数：$\red{N、M}$和$\red{T}$。第二行开始的$\red{N}$行，每行$\red{M}$个字符，“$\red{0}$”或“$\red{1}$”分别代表休眠状态与存活状态的细胞。

输出格式

输出$\red{N}$行，每行$\red{M}$个“$\red{0}$”或“$\red{1}$”，表示第$\red{T}$秒时的状态

样例

输入样例

5 5 1
00000
01100
01010
00100
00000

输出样例

00000
01100
01010
00100
00000

提示

$\red{1≤N, M≤100，1≤T≤64}$