题目描述

当拉格兰来到LowestWorld后，她——凭借观星者的敏锐——发现在遥远的天外存在着规律性闪动的星阵。经过了细致的观察，拉格兰发现：星阵是一个包含$n\times m$个星星的$n$行$m$列矩阵。每个星星都处于“闪亮”或者“黯淡”两种状态中的一种，星星每经过1个时间单位都会集体在一瞬间更新各自的状态。

对于一颗星星，如果此时它周围的8颗星星中有【大于等于4颗】或【小于等于1颗】处于“闪亮”状态，那么这颗星星在下一个时间单位会进入“黯淡”状态；如果有【恰好3颗】处于“闪亮”状态，那么这颗星星下一个时间单位会进入“闪亮”状态；如果有【恰好2颗】处于“闪亮”状态，那么这颗星星下一个时间单位的状态会保持不变，与本时间单位一致。对于一个位于星阵边界上的星星，可以等价地认为它周围没有星星的位置上存在着永久为“黯淡”状态的星星。

周围：以他自己为中心$3\times3$的区域内除了他自己的8个位置

为了节约观测资源，拉格兰决定让你使用卡戎的算力，根据她在$t=0$时刻观测到的星阵状态，推演出$t=T$时刻的星阵状态。

输入格式

第一行包括三个用空格分割的整数 $n,m,T(n,m\le 1000,T\le 100)$，分别代表了星阵的行数、列数和目标时刻$T$。

下面$n$行每行包括$m$个连续的字符，其中每个字符都是0或者1，分别代表这个星星处于“暗淡”状态或“闪亮”状态。

输出状态

输出包括$n$行，每行包括$m$个连续的字符。每个字符都应该是0或者1， 分别代表这个星星处于“暗淡”状态或“闪亮”状态。

样例

5 5 1
11111
11100
01101
00110
10010

10010
00001
10000
00001
00110

5 5 2
11111
11100
01101
00110
10010

00000
00000
00000
00010
00010

10 10 10
1011001101
1110101010
1010101010
1010100001
0110101010
1011010110
0011111100
1101010101
1110010101
1011101101

0111011000
1000000000
1011111000
1010000000
0100000000
0000000000
0000000000
0000110000
0000110000
0000000000

数据范围

本题共有10个测试点。

对于测试点1-2，$T = 1, n ≤ 3, m ≤ 3$。

对于测试点3-4，$T = 1$。

对于测试点5-6，$n, m ≤ 100$。

对于$100\%$的测试数据，$n, m ≤ 1000, T ≤ 100$。