Description

Code Jam 团队刚刚购买了一片果园，这片果园是一个 $1000$ 行 $1000$ 列的二维矩阵，每个格子都是未经准备的土壤。我们计划在这片果园里种植各种树木——AVL 树、二叉树、红黑树、伸展树等等——因此我们需要通过挖坑来准备一些格子：

• 为了保证每年有足够的树用于树类题目，我们需要至少有 $A$ 个准备好的格子。
• 为了便于照料树木，所有准备好的格子必须组成一个网格对齐的矩形，并且该矩形内的每一个格子都必须被准备好。

注意，上述要求还意味着，矩形外的格子都不能被准备。我们希望果园看起来整洁！

例如，当 $\mathbf A=11$ 时，虽然下图左侧的 11 个准备好的格子组成了一个 $3 \times 4$ 的矩形（即有 3 行 4 列），但该矩形中心的格子尚未准备好。因此，我们还没有完成果园的准备，因为 $3 \times 4$ 矩形内并非每个格子都已准备好。然而，只需再准备中心的那个格子，面积至少为 11 的矩形就被完全填满，果园也就准备好了。

下面是另一个例子。在这种情况下，$\mathbf{A}=6$。注意，中间的图在 $3\times 2$ 矩形之外准备了一个格子，因此虽然最右侧的图准备了一个面积为 6 的矩形，但所有准备好的格子并未组成一个矩形（因为左侧多了一个格子）。因此，果园还没有准备好。

挖坑对人类来说很辛苦，所以我们从 Google Go 团队借来了 Go gopher，并训练它来帮我们准备格子。我们可以通过给它一个目标格子的坐标来部署 gopher，但目标格子不能在矩阵的任意边界上。然而，我们的训练还不够完善，所以它会从以目标格子为中心的 $3\times 3$ 区块的九个格子中，均匀地（伪）随机选择一个格子，然后准备它。（如果它选择了一个已经准备好的格子，它会无用地再准备一次。）

我们最多只能部署 gopher $1000$ 次，否则它会太累而无法继续挖坑，所以我们需要你帮忙，制定一个策略来部署它。每次部署 gopher 后，你会被告知它实际准备了哪个格子，你可以据此决定下一步的部署。注意，你不需要提前声明矩形的尺寸或位置。

交互协议

本题为交互题，这意味着输入输出方式与标准 Code Jam 题目不同。你需要与一个独立的进程进行交互，该进程既向你提供信息，也会评判你的回答。所有信息都通过标准输入进入你的程序；你需要传达的信息应通过标准输出发送。请注意，许多编程语言默认会缓冲输出，因此在等待回应前，请确保你的输出已真正发送出去（例如，通过刷新缓冲区）。详见 FAQ 关于刷新缓冲区的说明。你通过标准错误输出的内容会被忽略，但可能会占用内存并计入内存限制，所以不要输出过多调试信息。为帮助你调试，题目末尾提供了本地测试工具脚本（Python 版）。此外，在 Number Guessing 的题解中还提供了所有支持语言的交互题样例代码。

最开始，你的程序应读取一行，包含一个整数 $\mathbf T$，表示测试用例的数量。然后，你需要处理 $\mathbf T$ 个测试用例。

对于每个测试用例，你的程序会读取一行，包含一个整数 $\mathbf A$，表示所需准备的最小矩形面积。然后，你的程序最多可以与评测机进行 $1000$ 次交互。

每次交互时，你需要通过标准输出发送一行，包含两个整数 $I$ 和 $J$，表示你希望部署 gopher 的行号和列号。两个整数都必须在 $2$ 到 $999$ 之间，且为十进制、无前导零。如果你的输出格式错误（如超出范围），你的程序会失败，评测机会返回一行 $-1 -1$，表示测试失败，之后不会再向你的输入流发送任何内容。否则，作为回应，评测机会向你的输入流输出一行，包含两个整数 $I'$ 和 $J'$，表示 gopher 实际准备的格子的行号和列号。

如果上一次部署后，所有准备好的格子组成了一个面积至少为 $\mathbf A$ 的矩形，你会收到 $I' = J' = 0$，表示该测试用例结束。否则，$I'$ 和 $J'$ 是 gopher 实际准备的格子的行号和列号，且满足 $\text{abs}(I'-I) \leq 1$ 且 $\text{abs}(J'-J) \leq 1$。然后，你可以开始下一次交互。

如果你的程序出现错误（如输出格式错误或超出范围），如上所述，评测机会返回 $I' = J' = -1$，之后不会再向你的输入流发送任何内容。如果你的程序在读取到 $I' = J' = -1$ 后仍然等待评测机，则会超时，导致 Time Limit Exceeded 错误。请注意，你有责任让程序及时退出，以获得正确的评判结果（Wrong Answer、Runtime Error 等），而不是 Time Limit Exceeded。和往常一样，如果总时间或内存超限，或程序运行时出错，你会收到相应的评判结果。

如果在 $1000$ 次部署内解决了测试用例，你会收到 $I' = J' = 0$ 的消息，然后继续解决下一个测试用例。如果 $1000$ 次交互后仍未解决该测试用例，评测机会返回 $I' = J' = -1$，之后不会再向你的输入流发送任何内容。

在解决所有测试用例后，你不应再向评测机发送任何信息。换句话说，如果你在收到最后一个测试用例的 $I' = J' = 0$ 消息后仍继续向标准输出打印内容，你会收到 Wrong Answer 的评判。

请注意，对于每个测试用例，gopher 从每个 $3 \times 3$ 区块中选择格子的方式是（伪）随机且彼此独立的，但对于同一个测试用例，每次的随机种子是相同的，因此对于同一个测试用例，错误的解法会始终错误。不同测试用例的随机种子不同。

Input Format

见交互协议。

Output Format

见交互协议。

Hint

交互样例

  t = readline_int()         // 读取 t=2
  a = readline_int()         // 读取 a=3
  printline 10 10 to stdout  // 输出 10 10，表示准备该格子
  flush stdout
  x, y = readline_two_int()  // 读取 10 11，表示实际准备了 10 11
  printline 10 10 to stdout  // 再次输出 10 10
  flush stdout
  x, y = readline_two_int()  // 读取 10 10，实际准备了 10 10
  printline 10 12 to stdout  // 输出 10 12
  flush stdout
  x, y = readline_two_int()  // 读取 10 11，再次准备了 10 11
  printline 10 10 to stdout  // 输出 10 10
  flush stdout
  x, y = readline_two_int()  // 读取 11 10，实际准备了 11 10
  printline 11 10 to stdout  // 输出 11 10
  flush stdout
  x, y = readline_two_int()  // 读取 0 0，表示 11 11 被准备好，形成了面积为 4 的矩形

上面的伪代码是某一测试组的前半部分交互样例。假设该测试组只有两个测试用例。伪代码首先读取测试用例数 $t$。然后开始第一个测试用例，假设 $\mathbf A = 3$（实际测试组中 $\mathbf A$ 只会是 $20$ 或 $200$）。伪代码首先读取 $a$，然后输出 $10\ 10$，请求准备该格子。由于（伪）随机选择，$10\ 11$ 被准备，于是读取 $10\ 11$。接着再次请求 $10\ 10$，这次 $10\ 10$ 被准备。随后输出 $10\ 12$，希望完成面积为 $3$ 的矩形，但只得到了 $10\ 11$。再次请求 $10\ 10$，这次 $11\ 10$ 被准备。注意，虽然准备好的面积已达 $3$，但还未形成矩形，因此继续准备。最后尝试 $11\ 10$，收到 $0\ 0$，表示 $11\ 11$ 被准备，完成了面积为 $4$ 的矩形（实际上是正方形）。因此，第一个测试用例成功解决。

  a = readline_int()         // 读取 a=3
  printline 10 10 to stdout  // 输出 10 10
  x, y = readline_two_int()  // 未刷新输出缓冲区，导致评测机阻塞

现在准备第二个测试用例。再次读取 $a=3$，并请求准备 $10\ 10$。但这次忘记刷新输出缓冲区！结果 $10\ 10$ 被缓冲，未发送给评测机。评测机和代码都在等待对方，最终导致超时。

  a = readline_int()         // 读取 a=3
  printline 1 1 to stdout    // 输出 1 1
  x, y = readline_two_int()  // 读取 -1 -1，因为 1 不在 [2, 999] 范围内
  printline 10 10 to stdout  // 仍然输出
  x, y = readline_two_int()  // 阻塞，因为评测机已停止发送信息

上面是另一个例子。假设第二个测试用例，代码记得刷新输出缓冲区，但输出了 $1\ 1$。注意，行列号必须都在 $[2, 999]$ 范围内，所以 $1\ 1$ 非法！评测机返回 $-1\ -1$。但代码在读取到 $-1\ -1$ 后仍然向评测机发送请求并等待，评测机已停止发送信息，最终导致超时。

注意，如果上述代码在读取到 $-1\ -1$ 后立即退出，则会收到 Wrong Answer：

  a = readline_int()         // 读取 a=3
  printline 1 1 to stdout    // 输出 1 1
  x, y = readline_two_int()  // 读取 -1 -1，因为 1 不在 [2, 999] 范围内
  exit                       // 收到 Wrong Answer 评判

你可以使用本地测试工具在本地或平台上测试。要在本地测试，你需要让测试工具与你的代码并行运行；你可以使用我们的 interactive runner。更多信息请阅读该文件中的注释说明。

测试工具的使用说明已包含在脚本注释中。建议你添加自己的测试用例。请注意，虽然测试工具旨在模拟评测系统，但它不是真正的评测系统，可能会有不同的表现。

数据范围

$1 \leqslant T \leqslant 20$。

测试点 1（10 分，可见）

• $A=20$。
• 整个测试点的时间限制：20 秒。

测试点 2（20 分，隐藏）

• $A=200$。
• 整个测试点的时间限制：60 秒。

由 ChatGPT 4.1 翻译