AT_agc077_e.[AGC077E] Hamiltonian Path Inversion

$ 4\times 500 $ のグリッドグラフの各頂点に $ 0 $ または $ 1 $ を書き込むことを考えます． $ N=0,1,\ldots,999899,999900 $ に対して以下の条件を満たすことができるように上手に書き込んでください．

• グリッドグラフのハミルトンパスであって，そのパスの頂点に書かれた数を並べて得られる列の転倒数が $ N $ であるようなものが存在する．

$ 3\times 4 $ の例．この書き込み方では $ N = 10, 11, \ldots, 20 $ が達成可能である．

---

この問題は インタラクティブ な問題です．問題文中のパラメータは $ H=4,W=500,Q=200 $ で固定されています．

あなたとジャッジは下記の手順を行います．手順はフェイズ $ 1 $ とフェイズ $ 2 $ からなり，まずフェイズ $ 1 $ を行った直後，続けてフェイズ $ 2 $ を行います．

（フェイズ $ 1 $ ）

各要素が $ 0 $ または $ 1 $ である $ H\times W $ 行列 $ A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) $ を出力してください．

（フェイズ $ 2 $ ）

以下の問題を $ Q $ 回解いてください．

ジャッジから整数 $ N $ が与えられる．
$ H $ 行 $ W $ 列のグリッドを考える．上から $ i $ 行目，左から $ j $ 列目のマス $ (i,j) $ には整数 $ A_{i,j} $ が書かれている．
好きなマスから開始し，上下左右に隣接するマスへの移動を繰り返して $ HW $ 個すべてのマスをちょうど一度ずつ通り，好きなマスで終わる長さ $ HW $ の経路 $ P $ であって，以下を満たすものを一つ求めよ．

• $ P $ で通るマスに書かれた整数を順に並べて得られる長さ $ HW $ の数列の転倒数は $ N $ である．

Input & Output Format

この問題はインタラクティブな問題である．

最初に $ H,W,Q $ が標準入力から与えられる．

$ H $ $ W $ $ Q $

（フェイズ $ 1 $ ）

各要素が $ 0 $ または $ 1 $ である $ H\times W $ 行列 $ A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) $ を $ H $ 行に渡って出力せよ．

$ i $ 行目には， $ A_{i,1}A_{i,2}\ldots A_{i,W} $ を長さ $ W $ の 0 と 1 からなる文字列として出力せよ．

$ A_{1,1}A_{1,2}\ldots A_{1,W} $ $ A_{2,1}A_{2,2}\ldots A_{2,W} $ $ \vdots $ $ A_{H,1}A_{H,2}\ldots A_{H,W} $

（フェイズ $ 2 $ ）

$ Q $ 回問題を解く．各問題では，まず整数 $ N $ が標準入力から与えられる．

$ N $

（なお，直前の問題が不正解だったり， $ A $ や経路の出力形式が誤っていたりした場合，ここでは $ N $ の代わりに -1 が標準入力から与えられる．この場合はただちにプログラムを正常終了すること．ただし， $ Q $ 個目の問題で初めて誤った出力を行った場合，その後の入力は何も与えられない．）

その後，条件を満たす経路 $ P $ を， $ i $ 番目に訪れるマスを $ (x_i, y_i) $ として以下の形式で出力せよ．

$ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_{HW} $ $ y_{HW} $

$ x_i,y_i $ は以下を満たす必要がある．

• $ 1\leq x_i\leq H, 1\leq y_i\leq W $
• $ i\neq j $ ならば $ (x_i,y_i)\neq (x_j,y_j) $
• $ i=1,2,\ldots,HW-1 $ に対し $ |x_i-x_{i+1}|+|y_i-y_{i+1}|=1 $
• 数列 $ (A_{x_1,y_1}, A_{x_2,y_2},\ldots,A_{x_{HW},y_{HW}}) $ の転倒数は $ N $

null

null

注意点

• ジャッジから -1 という入力を受け取った場合はただちにプログラムを正常終了してください．終了した場合のジャッジ結果は WA となりますが，終了しなかった場合のジャッジ結果は不定です．
• 出力を行うたびに，末尾に改行を入れて標準出力を flush してください．そうしない場合，ジャッジ結果が TLE となる可能性があります．
• 余分な改行は不正な形式の出力とみなされるため，行わないでください．
• フェイズ $ 2 $ を終了したらただちにプログラムを終了してください．そうしない場合，ジャッジ結果は不定です．

入出力例

以下は， $ H=3,W=4,Q=2 $ の場合の入出力例です．

この例は制約を満たさないので，ジャッジには含まれません．

   入力 出力 説明     ```

3 4 2

   $ H,W,Q $  が与えられます．   ```

1101
0110
1010

$ A=\begin{pmatrix} 1&1&0&1 \ 0&1&1&0 \ 1&0&1&0 \end{pmatrix} $ を出力します． ```

10

   $ 1 $  つ目の問題の  $ N $  が与えられます．    ```

3 2
3 3
3 4
2 4
1 4
1 3
2 3
2 2
1 2
1 1
2 1
3 1

$ (3,2)\to(3,3)\to(3,4)\to(2,4)\to(1,4)\to(1,3)\to(2,3)\to(2,2)\to(1,2)\to(1,1)\to(2,1)\to(3,1) $ という経路を出力します．この経路で通るマスに書かれた整数を順に並べて得られる数列は $ (0,1,0,0,1,0,1,1,1,1,0,1) $ であり，この数列の転倒数は $ 10 $ であるため条件を満たします． ```

15

   $ 2 $  つ目の問題の  $ N $  が与えられます．    ```

1 1
2 1
3 1
3 2
3 3
3 4
2 4
2 3
2 2
1 2
1 3
1 4

$ (1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)\to(3,4)\to(2,4)\to(2,3)\to(2,2)\to(1,2)\to(1,3)\to(1,4) $ という経路を出力します．この経路で通るマスに書かれた整数を順に並べて得られる数列は $ (1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1) $ であり，この数列の転倒数は $ 15 $ であるため条件を満たします．

Constraints

• $ H=4,W=500,Q=200 $
• $ 0\leq N\leq 999900 $
• 入力される数値は全て整数