問題背景
著名な数学者ジョン・ホートン・コンウェイ（John H. Conway, 1937–2020）は、新型コロナウイルス感染症の流行下で惜しまれつつこの世を去りました。彼の研究分野は組合せゲーム理論や群論など多岐にわたり、有限単純群の分類、セル・オートマトン、組合せゲーム理論において重要な貢献をしました。また、数学の普及にも尽力し、世界中で一世を風靡した「ライフゲーム（Conway's Game of Life）」を考案したことでも知られています。
今日、彼の最も有名な発明の一つを振り返ってみましょう。
ライフゲームのルールは以下の通りです。
- 正方形のグリッドがあり、各セルには細胞が存在し、細胞は「死亡」または「生存」のいずれかの状態をとります。各細胞の次の瞬間の状態は、現在の状態と周囲 8 つのセルの状態によって一意に決定されます。
- 現在生存している細胞について、周囲の生存細胞が 2 つ未満（2 つを含まない）の場合、その細胞は死亡状態になります。
- 現在生存している細胞について、周囲の生存細胞が 2 つまたは 3 つの場合、その細胞は状態を維持します。
- 現在生存している細胞について、周囲の生存細胞が 3 つを超える場合、その細胞は死亡状態になります。
- 現在死亡している細胞について、周囲の生存細胞がちょうど 3 つの場合、その細胞は生存状態になります。それ以外の場合は死亡状態のままです。
問題文
コンピュータのメモリ制限のため、無限に広がるグリッド上のライフゲームをシミュレートすることはできません。そのため、ここでは $4\times 4$ のグリッド上のライフゲームのみを考えます。すなわち、グリッドの外側では細胞は生存できないものとします。
$Q$ 個のクエリが与えられます。各クエリでは、$4\times 4$ グリッドの各セルの初期状態が与えられます。$T$ ステップ経過後の各セルの状態を求めてください。
入力
標準入力からデータを読み込みます。
1 行目にクエリの数を示す正整数 $Q$ が与えられます。
続く $5Q$ 行は、5 行ごとに 1 つのクエリを表します。
各クエリの最初の 4 行は、それぞれ長さ 4 の 01 文字列です。これはグリッドの各セルの状態を表しており、0 は死亡、1 は生存を意味します。続く 1 行には、経過するステップ数を示す正整数 $T$ が与えられます。
出力
標準出力に書き出します。
$4Q$ 行を出力し、4 行ごとに 1 つのクエリに対する答えを表します。
各クエリの答えとして、長さ 4 の 01 文字列を 4 行出力してください。これはグリッドの各セルの状態を表しており、0 は死亡、1 は生存を意味します。
入出力例
入力 1
1
0000
1100
0110
0000
3出力 1
0100
1010
1010
0100注記
1 ステップ経過後のグリッドの状態は以下の通りです。
0000 1110 1110 0000
さらに 1 ステップ経過後のグリッドの状態は以下の通りです。
0100 1010 1010 0100
次のステップの状態はこの状態と同じになるため、以降のステップでもこの状態が維持されます。したがって、開始から 3 ステップ経過後の状態は上記の通りとなります。
入力 2
ダウンロードディレクトリ内の ex_2.in および ex_2.ans を参照してください。
小課題
すべてのデータにおいて、$Q \le 10^{4}, T \le 10^{9}$ を満たします。
| テストケース | $Q$ | $T$ |
|---|---|---|
| 1, 2, 3, 4 | $= 10^{2}$ | $\le 10^{2}$ |
| 5, 6, 7 | $= 10^{3}$ | $\le 10^{3}$ |
| 8, 9 | $= 10$ | $\le 10^{9}$ |
| 10 | $= 10^{4}$ | $\le 10^{9}$ |