测试数据来自 oistream/1140

背景

• Idea: 北京市赛
• Data: 暂无
• Std: 北京市赛
• 题面: 北京市赛+oistream

---

著名数学家约翰·康威（\(\text{John H. Conway,1937}\sim\text{2020}\)）不幸于新冠肺炎疫情中去世。他的研究兴趣涵盖组合游戏、群论等多个领域，在有限群分类、元胞自动机和组合游戏上做出了重要的贡献；他致力于数学科普，设计了曾风靡全球的“康威生命游戏”（\(\text{Conway's Game of Life}\)）。

今天，让我们来回顾他最著名的发明之一。

生命游戏的规则如下：

1. 有一个正方形网格，每个格子中有一个细胞，细胞有两种状态：死亡或存活。每个细胞在下一刻的状态都由其现在的状态以及周围 \(8\) 个细胞的状态唯一确定。
2. 当前细胞为存活状态时，如果它周围的存活细胞低于 \(2\) 个（不包含 \(2\) 个），该细胞变成死亡状态。
3. 当前细胞为存活状态时，如果它周围有 \(2\) 个或 \(3\) 个存活细胞，该细胞保持原样。
4. 当前细胞为存活状态时，如果它周围有超过 \(3\) 个存活细胞，该细胞变成死亡状态。
5. 当前细胞为死亡状态时，当周围有 \(3\) 个存活细胞，该细胞变成存活状态，否则仍是死亡状态。

描述

由于计算机内存限制，我们无法模拟无限大的网格上的生命游戏，因此我们只考虑 \(4\times 4\) 网格上的生命游戏，即认为**网格外禁止细胞存活**。

接下来你有 \(Q\) 组询问，每次给你一个 \(4\times 4\) 网格上的每个格子状态。问你 \(T\) 个时刻之后网格上每个格子的状态。

输入格式

• 第一行输入一个正整数 \(Q\)，表示询问组数。
• 接下来 \(5\times Q\) 行，每 \(5\) 行表示一组询问。
  • 每组询问前 \(4\) 行每行一个长为 \(4\) 的 01 组成的字符串。表示这个网格上每个格子的细胞状态，其中 0 表示死亡，1 表示存活；接着一行一个正整数 \(T\)，表示接下来经过多少个时刻。

输出格式

输出 \(4\times Q\) 行，每 \(4\) 行表示一组询问对应的答案。

每组询问的答案，每行一个长为 \(4\) 的 01 组成的字符串。表示这个网格上每个格子的细胞状态，其中 0 表示死亡，1 表示存活。

样例

输入样例1

1
0000
1100
0110
0000
3

输出样例1

0100
1010
1010
0100

样例解释1

经过一个时刻后，网格状态变为

0000
1110
1110
0000

再经过一个时刻后，网格状态变为

0100
1010
1010
0100

然后下一个状态会与该状态相同，也就是说接下来的时刻永远都会保持这一状态。因此从开始经过 \(3\) 个时刻后是该状态。

输入样例2

见附加文件。

输出样例2

见附加文件。

数据规模与约定

对于 \(100\%\) 的数据，保证 \(Q\leq 10^4, T\leq 10^9\)。