AT_agc077_e [AGC077E] Hamiltonian Path Inversion

> Consider writing $ 0 $ or $ 1 $ on each vertex of a $ 4\times 500 $ grid graph. Write the values cleverly so that for each $ N=0,1,\ldots,999899,999900 $ , the following condition is satisfied. > > - There exists a Hamiltonian path on the grid graph such that the sequence of numbers written on the vertices along the path has an inversion count of $ N $ . > > An example with $ 3\times 4 $ . With this assignment, $ N = 10, 11, \ldots, 20 $ are achievable. --- This is an **interactive** problem. **The parameters in the problem statement are fixed at $ H=4,W=500,Q=200 $ .** You and the judge perform the following steps. The steps consist of Phase $ 1 $ and Phase $ 2 $ ; Phase $ 1 $ is performed first, immediately followed by Phase $ 2 $ . (Phase $ 1 $ ) Output an $ H\times W $ matrix $ A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) $ where each element is $ 0 $ or $ 1 $ . (Phase $ 2 $ ) Solve the following problem $ Q $ times. > The judge gives you an integer $ N $ . > Consider an $ H $ -row $ W $ -column grid. The cell $ (i,j) $ , located at the $ i $ -th row from the top and the $ j $ -th column from the left, has the integer $ A_{i,j} $ written on it. > Find a path $ P $ of length $ HW $ that starts at any cell, moves to an adjacent cell (up, down, left, or right) repeatedly, visits all $ HW $ cells exactly once, and ends at any cell, such that the following is satisfied. > > - The inversion count of the sequence of length $ HW $ obtained by listing the integers written on the cells visited by $ P $ in order is $ N $ .

N/A

N/A

### Interaction This is an interactive problem. First, $ H,W,Q $ are given from Standard Input. > $ H $ $ W $ $ Q $ (Phase $ 1 $ ) Output an $ H\times W $ matrix $ A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) $ where each element is $ 0 $ or $ 1 $ , over $ H $ lines. The $ i $ -th line should contain $ A_{i,1}A_{i,2}\ldots A_{i,W} $ as a string of length $ W $ consisting of `0` and `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} $ (Phase $ 2 $ ) Solve the problem $ Q $ times. For each problem, first an integer $ N $ is given from Standard Input. > $ N $ (Note: if your answer to the previous problem was incorrect, or if $ A $ or the path was output in an incorrect format, then instead of $ N $ , `-1` is given from Standard Input here. In that case, immediately terminate the program normally. However, if an incorrect output is given for the first time in the $ Q $ -th problem, no further input will be given.) Then, output a path $ P $ satisfying the condition, where the $ i $ -th visited cell is $ (x_i, y_i) $ , in the following format: > $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_{HW} $ $ y_{HW} $ $ x_i $ and $ y_i $ must satisfy the following. - $ 1\leq x_i\leq H, 1\leq y_i\leq W $ . - $ (x_i,y_i)\neq (x_j,y_j) $ if $ i\neq j $ . - $ |x_i-x_{i+1}|+|y_i-y_{i+1}|=1 $ for $ i=1,2,\ldots,HW-1 $ . - The inversion count of the sequence $ (A_{x_1,y_1}, A_{x_2,y_2},\ldots,A_{x_{HW},y_{HW}}) $ is $ N $ . ### Notes - **If you receive `-1` as input from the judge, immediately terminate the program normally. If you terminate, the verdict will be WA; otherwise, the verdict is indeterminate.** - **In each output, include a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.** - **Extra newlines in output are considered as malformed; do not include them.** - Terminate your program immediately after finishing Phase $ 2 $ . Otherwise, the verdict is indeterminate. ### Sample Interaction Below is a sample interaction for the case $ H=3,W=4,Q=2 $ . This example does not satisfy the constraints and is not included in the judge. Input Output Explanation ``` 3 4 2 ``` $ H,W,Q $ are given. ``` 1101 0110 1010 ``` Output $ A=\begin{pmatrix} 1&1&0&1 \\ 0&1&1&0 \\ 1&0&1&0 \end{pmatrix} $ . ``` 10 ``` $ N $ for the first problem is given. ``` 3 2 3 3 3 4 2 4 1 4 1 3 2 3 2 2 1 2 1 1 2 1 3 1 ``` Output the path $ (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) $ . The sequence of integers written on the cells visited along this path is $ (0,1,0,0,1,0,1,1,1,1,0,1) $ , and the inversion count of this sequence is $ 10 $ , so the condition is satisfied. ``` 15 ``` $ N $ for the second problem is given. ``` 1 1 2 1 3 1 3 2 3 3 3 4 2 4 2 3 2 2 1 2 1 3 1 4 ``` Output the path $ (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) $ . The sequence of integers written on the cells visited along this path is $ (1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1) $ , and the inversion count of this sequence is $ 15 $ , so the condition is satisfied. ### Constraints - $ H=4,W=500,Q=200 $ - $ 0\leq N\leq 999900 $ - All input values are integers.