Daniel has an $N \times N$ grid where each cell is colored either black or white. The state of this grid is represented by an $N \times N$ matrix $A$ where each element is 0 or 1. For $0 \le i, j \le N - 1$, $A[i][j] = 1$ means the cell in the $i$-th row and $j$-th column (hereafter referred to as cell $(i, j)$) is black, and $A[i][j] = 0$ means it is white. It is known that there exist no $(i_1, i_2, j_1, j_2)$ in the grid satisfying the following conditions:

1. $0 \le i_1 < i_2 \le N - 1, 0 \le j_1 < j_2 \le N - 1$
2. $A[i_1][j_1] = A[i_2][j_2], A[i_1][j_2] = A[i_2][j_1], A[i_1][j_1] \neq A[i_1][j_2]$

Daniel wants to transmit the grid to Young-wook. For security reasons, the communication follows this procedure:

1. Daniel selects some of the $N^2$ total cells.
2. The communication system possesses secret permutations $X$ and $Y$ of $(0, 1, 2, \dots, N - 1)$.
3. An $N \times N$ matrix $B$ is transmitted to Young-wook. For each cell $(i, j)$ selected by Daniel, $B[X[i]][Y[j]] = A[i][j]$ holds, and for each cell $(i, j)$ not selected, $B[X[i]][Y[j]] = -1$ holds.

Young-wook must recover the parts filled with $-1$ in matrix $B$ such that $B[X[i]][Y[j]] = A[i][j]$ holds for all $0 \le i, j \le N - 1$.

Implementation Details

You must implement the following functions:

void send(std::vector<std::vector<int> > A)

• $A$: A 2D vector of size $N$. Each element vector also has size $N$.
• You must call the select function within this function to choose the cells to transmit.

void select(int i, int j)

• Must satisfy $0 \le i, j \le N - 1$ when called.
• Let $K$ be the total number of times this function is called.

vector<vector<int> > reconstruct(vector<vector<int> > B)

• The grader possesses permutations $X$ and $Y$ of $(0, 1, \dots, N - 1)$.
• For the original 2D vector $A$ given in send, $B$ is provided as a parameter satisfying the following conditions:
  • $B$ is a 2D vector of the same shape as $A$.
  • For $0 \le i, j \le N - 1$, if select(i, j) was called in the send function, $B[X[i]][Y[j]] = A[i][j]$ holds.
  • For $0 \le i, j \le N - 1$, if select(i, j) was never called in the send function, $B[X[i]][Y[j]] = -1$ holds.
• The return value $C$ of the function must satisfy $C[X[i]][Y[j]] = A[i][j]$ for all $0 \le i, j \le N - 1$.

The select calls in send and the return value of reconstruct must depend only on the values of the given parameters. If different behaviors occur when calling the functions multiple times with the same parameter values, it may be treated as an incorrect answer.

In the grading process, the permutations $X$ and $Y$ are predetermined and non-adaptive. However, the participant cannot access them; in the sample grader, $X$ and $Y$ are provided as input.

Each input consists of multiple independent test cases. For each test case, send and reconstruct are called once each. There is no guarantee that send and reconstruct are called in the order of the test cases, but it is guaranteed that they operate as described based on the function calls and return values.

Unlike the sample grader, your program is executed twice for each input during actual grading. In the first execution, send is called for each test case to output the results, and in the second execution, the output of the first execution is taken as input to run reconstruct. For each test case, the execution time on the competition system is measured as the sum of the execution times of the two program runs, and memory usage is also measured as the sum of the memory usage of the two runs. Time and memory limits are based on the combined results of the two runs. Since send is only called in the first run, the constraint on the number of select calls is not affected by the two-run execution.

Do not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N \le 500$
• The number of calls $K$ to select within send cannot exceed $N^2$.
• The sum of $N^2$ over all test cases does not exceed $10^6$.

Subtasks

1. (12 points)
   • For $0 \le i, j \le N - 1$, $i \le j$ is equivalent to $A[i][j] = 1$.
2. (35 points)
   • The grid is in the form of a histogram. That is, for every $0 \le j \le N - 1$, there exists $H_j$ such that $0 \le H_j \le N$, where $A[i][j] = 1$ if $i < H_j$, and $A[i][j] = 0$ otherwise.
3. (53 points)
   • No additional constraints.

If the return value $C$ of the reconstruct function satisfies $C[X[i]][Y[j]] = A[i][j]$, partial points are awarded for each subtask as follows. If the condition is not met, 0 points are awarded.

For the size $N$ of $A$ and the number of calls $K$ to select:

• If $K \le 2N - 1$ is satisfied for all test cases, full points are awarded.
• Otherwise, for the smallest integer $c$ satisfying $c \cdot N \ge K$, if $c \le 10$, you receive $\frac{110-9c}{100}$ of the subtask points.
• If the above two conditions are not met and $K \le \frac{N^2}{2} + 1$ is satisfied, you receive $\frac{7}{100}$ of the subtask points.
• If none of the above three conditions are met, no points are awarded for the subtask.

Examples

Input 1

N = 3, A = [[1, 1, 1], [1, 1, 0], [0, 1, 0]], X = [2, 1, 0], Y = [0, 1, 2]

The grader first calls the send function.

send([[1, 1, 1], [1, 1, 0], [0, 1, 0]])

Suppose the function calls within send were as follows:

select(0, 1)
select(0, 2)
select(1, 0)
select(2, 2)

Then the grader calls the function as follows:

reconstruct([[-1, -1, 0], [1, -1, -1], [-1, 1, 1]])

Since the return value $C$ of the reconstruct function must satisfy $C[X[i]][Y[j]] = A[i][j]$ for all $0 \le i, j \le N - 1$, reconstruct([[-1, -1, 0], [1, -1, -1], [-1, 1, 1]]) must return [[0, 1, 0], [1, 1, 0], [1, 1, 1]].

Sample grader

The sample grader receives the number of test cases $T$ as input. Thereafter, it receives the following information $T$ times:

• Line 1: $N$
• Line 2 + $k$ ($0 \le k \le N - 1$): $A[k][0] \ A[k][1] \ \dots \ A[k][N - 1]$
• Line $N + 2$: $X[0] \ X[1] \ \dots \ X[N - 1]$
• Line $N + 3$: $Y[0] \ Y[1] \ \dots \ Y[N - 1]$

The sample grader outputs the following for each test case:

• If the called select(i, j) does not satisfy $0 \le i, j \le N - 1$, it outputs Wrong Answer [1] on a single line.
• If the number of calls to the select function exceeds $N^2$, it outputs Wrong Answer [2] on a single line.
• If the return value of the reconstruct function is not in the same form as $B$, it outputs Wrong Answer [3] on a single line.
• If the return value of the reconstruct function fails to restore the matrix to satisfy the conditions, it outputs Wrong Answer [4] on a single line.
• Otherwise, it outputs the number of calls to the select function, e.g., K: 10.

If Wrong Answer is output, the sample grader terminates immediately. Note that the sample grader may differ from the grader used in actual scoring.