题目描述

给定一个 $n \times m$ 的棋盘，. 表示死细胞，# 表示活细胞。每个细胞的状态按下面的规则同时更新：

• 若一个活细胞周围八格中恰有 2 或 3 个活细胞，则下一代仍活着，否则死亡；
• 若一个死细胞周围八格中恰有 3 个活细胞，则下一代复活，否则保持死亡。

请输出经过 $k$ 代之后棋盘的样子。

输入格式

第一行三个整数 $n, m, k$（$1 \le n, m \le 100$，$1 \le k \le 1000$）。

接下来 $n$ 行，每行 $m$ 个字符，描述棋盘。

输出格式

共 $n$ 行，每行 $m$ 个字符，表示 $k$ 代之后的棋盘。

样例 1

输入：

1 3 1
###

输出：

.#.

（三个活细胞是"闪烁灯"：横着的一排在下一代变成竖着的一排。若再来一代又会变回去。）

样例 2

输入：

6 6 4
......
.#....
...#..
.###..
......
......

输出：

......
......
...#..
....#.
..###.
......

（这就是著名的"滑翔机"：4 代之后图案整体向右下平移了一格，细胞数仍然是 5 个。）

提示

模拟的关键是"同时更新"：必须先把新棋盘算在一个新的二维数组里，全部算完之后再整体替换；绝对不能边算边改原棋盘，否则同一个细胞会被它已经更新过的邻居影响。

遍历八个邻居可以用两个长度为 8 的偏移数组：

dx = {-1,-1,-1, 0, 0, 1, 1, 1}
dy = {-1, 0, 1,-1, 1,-1, 0, 1}