这是一道通信题

你有一个 $N \times N$ 的网格，每个格子被涂成黑色或白色。这个网格的状态可以用一个 $N \times N$ 的矩阵 $A$ 来表示，其中每个元素是 $0$ 或 $1$。对于 $0 \leq i, j \leq N-1$，如果 $A[i][j]=1$，则表示第 $i$ 行第 $j$ 列的格子（以下简称格子 $(i, j)$）是黑色；如果 $A[i][j]=0$，则表示该格子是白色。此外，已知这个网格满足以下条件：不存在一组 $\left(i_{1}, i_{2}, j_{1}, j_{2}\right)$ 同时满足：

1. $0 \leq i_{1} < i_{2} \leq N-1, 0 \leq j_{1} < j_{2} \leq N-1$
2. $A\left[i_{1}\right]\left[j_{1}\right] = A\left[i_{2}\right]\left[j_{2}\right], A\left[i_{1}\right]\left[j_{2}\right] = A\left[i_{2}\right]\left[j_{1}\right], A\left[i_{1}\right]\left[j_{1}\right] \neq A\left[i_{1}\right]\left[j_{2}\right]$

你想把这个网格传递给戴江齐。由于安全原因，传输过程需要遵循以下步骤：

1. 你从总共 $N^{2}$ 个格子中挑选出若干个格子。
2. 通信系统持有一对秘密排列 $X$ 和 $Y$，它们是 $(0, 1, 2, \ldots, N-1)$ 的某种顺序。
3. 一个 $N \times N$ 的矩阵 $B$ 会被传递给戴江齐。对于你选中的每个格子 $(i, j)$，$B[X[i]][Y[j]] = A[i][j]$ 成立；对于未被选中的格子 $(i, j)$，$B[X[i]][Y[j]] = -1$ 成立。

戴江齐的任务是根据矩阵 $B$，将其中值为 $-1$ 的部分还原，使得对所有 $0 \leq i, j \leq N-1$，都有 $B[X[i]][Y[j]] = A[i][j]$ 成立。

实现细节

你需要实现以下几个函数：

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

• $A$：一个大小为 $N$ 的二维向量，每个子向量的长度也是 $N$。
• 在这个函数中，你需要调用 select 函数来选择要传输的格子。

void select(int i, int j)

• 调用时需满足 $0 \leq i, j \leq N-1$。
• 这个函数被调用的总次数记为 $K$。

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

• 评测程序持有一对 $(0, 1, \ldots, N-1)$ 的排列 $X$ 和 $Y$。
• 输入参数 $B$ 是根据 send 函数中给定的二维向量 $A$ 生成的，满足以下条件：
  • $B$ 与 $A$ 的形状相同。
  • 对于 $0 \leq i, j \leq N-1$，如果 send 函数中调用了 select(i, j)，则 $\mathrm{B}[\mathrm{X}[\mathrm{i}]][\mathrm{Y}[\mathrm{j}]] = \mathrm{A}[\mathrm{i}][\mathrm{j}]$ 成立。
  • 对于 $0 \leq i, j \leq N-1$，如果 send 函数中未调用 select(i, j)，则 $B[X[i]][Y[j]] = -1$ 成立。
• 函数返回的矩阵 $C$ 必须满足：对于所有 $0 \leq i, j \leq N-1$，$C[X[i]][Y[j]] = A[i][j]$。

send 函数中 select 的调用以及 reconstruct 函数的返回值只能依赖于输入参数的值。如果同一个参数值多次调用函数时行为不一致，可能会被判为错误答案。

评测过程中，排列 $X$ 和 $Y$ 是预先确定且非自适应的（non-adaptive），但你无法直接访问它们。在示例评测程序中，$X$ 和 $Y$ 会作为输入提供。

每个输入包含若干独立的测试数据。每个测试数据会分别调用一次 send 和 reconstruct 函数。虽然不保证函数按测试数据顺序调用，但保证其调用和返回值符合题目描述的逻辑。

与示例评测程序不同，实际评测时，你的程序会为每个输入运行两次。第一次运行时，对每个测试数据调用 send 函数并输出结果；第二次运行时，以第一次的输出作为输入，调用 reconstruct 函数。每个测试数据的执行时间是两次运行时间的总和，内存使用量也是两次运行的总和。时间和内存限制以两次运行的总和为准。由于 select 函数只在第一次运行中调用，其调用次数限制不受两次运行影响。

你提交的源代码中不得包含任何输入输出函数。

样例

考虑 $N=3$，$A=[[1,1,1],[1,1,0],[0,1,0]]$，$X=[2,1,0]$，$Y=[0,1,2]$ 的情况。

评测程序首先调用：

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

假设 send 函数中调用了以下内容：

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

之后，评分程序调用：

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

reconstruct 函数的返回值 $C$ 必须满足所有 $0 \leq i, j \leq N-1$ 的 $C[X[i]][Y[j]] = \mathrm{A}[\mathrm{i}][\mathrm{j}]$，因此 reconstruct([[-1, -1, 0], [1, -1, -1], [-1, 1, 1]]) 应返回 $[[0,1,0],[1,1,0],[1,1,1]]$。

子任务

对于所有输入数据，满足：

• $1 \leq N \leq 500$
• send 函数中 select 的调用次数 $K$ 不得超过 $N^{2}$。
• 所有测试数据中 $N^{2}$ 的总和不超过 $10^{6}$。

详细子任务附加限制及分值如下表所示。

如果 reconstruct 函数的返回值 $C$ 满足 $C[X[i]][Y[j]] = A[i][j]$，则各子问题的得分如下。若不满足此条件，则得 $0$ 分。

根据 $A$ 的大小 $N$ 和 select 的调用次数 $K$：

• 如果所有测试用例满足 $K \leq 2N-1$，则获得满分。
• 否则，找到满足 $c \cdot N \geq K$ 的最小整数 $c$：
  • 若 $c \leq 10$，则获得子问题分数的 $\frac{110 - 9c}{100}$。
• 若上述条件均不满足，但 $K \leq \frac{N^{2}}{2} + 1$，则获得子问题分数的 $\frac{7}{100}$。
• 若以上条件均不满足，则该子问题得 $0$ 分。

样例交互库

示例评测程序会接收测试数据数量 $T$，然后依次接收 $T$ 组输入，每组包括：

• 第 $1$ 行：$N$
• 第 $2+k$ $(0 \leq k \leq N-1)$ 行：$A[k][0]\ A[k][1]\ \cdots\ A[k][N-1]$
• 第 $N+2$ 行：$X[0]\ X[1]\ \cdots\ X[N-1]$
• 第 $N+3$ 行：$Y[0]\ Y[1]\ \cdots\ Y[N-1]$

示例评测程序对每个测试数据输出：

• 若调用的 select(i, j) 不满足 $0 \leq i, j \leq N-1$，输出一行 Wrong Answer [1]。
• 若 select 调用次数超过 $N^{2}$，输出一行 Wrong Answer [2]。
• 若 reconstruct 返回值与 $B$ 形状不一致，输出一行 Wrong Answer [3]。
• 若 reconstruct 返回值未能正确还原矩阵，输出一行 Wrong Answer [4]。
• 其他情况下，输出如 K: 10，表示 select 的调用次数。

一旦输出 Wrong Answer，示例评测程序立即终止。

请注意，示例评测程序可能与实际评测程序有所不同。