Problem Statement

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$.

Constraints

• $H=4,W=500,Q=200$
• $0\leq N\leq 999900$
• All input values are integers.

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$.

Note

• 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.