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.

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.

3 4 2

1101
0110
1010

10

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

15

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