まず、入力が以下の形式で標準入力から与えられる。

N M Q
P_{1, 1} P_{1, 2} P_{1, 3} P_{1, 4}
P_{2, 1} P_{2, 2} P_{2, 3} P_{2, 4}
...
P_{N \times M, 1} P_{N \times M, 2} P_{N \times M, 3} P_{N \times M, 4}

• パズルの縦幅 N、横幅 M ( 2 \leq N, M \leq 8 ) 、質問回数の上限 Q ( 3 \leq Q \leq 10000 ) が、スペースで区切られて、それぞれ整数で与えられる。
• 続く N \times M 行で、i 番目のピースの上辺 P_{i, 1}、右辺 P_{i, 2}、下辺 P_{i, 3}、左辺 P_{i, 4}が与えられる。ただし、P_{i, j} = 0は直線、P_{i, j} = 1は凸、P_{i, j} = 2は凹を意味する。

あなたのプログラムは、2つのピースのある辺と辺が繋がるかどうかを、以下の形式で標準出力を用いて質問することができる。

? a d_a b d_b

• a 番目のピースの方向 d_a の辺と、b 番目のピースの方向 d_b の辺をつなげるのが正解かどうかを質問する。
• 1 \leq a, b \leq N \times M
• d_a, d_bは、上辺を1、右辺を2、下辺を3、左辺を4とする。
• 応答プログラムは、質問された辺がつながるのが正解であればyesを、そうでなければnoを出力する。

最後に、ジグソーパズルの並べ方を以下の形式で標準出力を用いて回答する。

!
p_{1, 1} d_{1, 1} p_{1, 2} d_{1, 2} ... p_{1, M} d_{1, M}
p_{2, 1} d_{2, 1} p_{2, 2} d_{2, 2} ... p_{2, M} d_{2, M}
...
p_{N, 1} d_{N, 1} p_{N, 2} d_{N, 2} ... p_{N, M} d_{N, M}

• i 行目の j 列目に p_{i, j} 番目のピースを入力で与えられた上辺を方向 d_{i, j} にして置く。
• d_{i, j} は、上を1、右を2、下を3、左を4とする。
• ジグソーパズル全体の向きは問わない。すなわち、ジグソーパズル全体が正解に対して180度回転していても構わない。N = Mであれば90度または270度回転していても構わない。

• Q = 10000 の入力に正解すると、160 点満点に対して部分点として、50 点が与えられる。
• Q = 3000 の入力に正解すると、160 点満点に対して部分点として、上記とは別に 60 点が与えられる。
• 残り 50 点に対しては 25 の入力があり、入力を一つ正解するごとに部分点として 2 点が与えられる。各入力の N, M, Q を下表に示す。

  	N	M	Q
  1	5	7	1000
  2	7	5	1000
  3	8	5	1000
  4	5	8	1000
  5	6	6	1000
  6	6	6	1000
  7	5	6	500
  8	6	5	500
  9	5	5	500
  10	4	6	500
  11	6	4	500
  12	4	5	200
  13	5	4	200
  14	4	4	100
  15	4	4	80
  16	4	4	70
  17	4	3	50
  18	3	4	40
  19	3	4	25
  20	3	3	25
  21	3	3	15
  22	2	3	10
  23	2	3	7
  24	2	2	5
  25	2	2	3