Code Jam 团队刚刚购买了一个果园，这是一个 $1000 \times 1000$ 的未开垦土壤网格。我们计划利用这个果园种植各种树木——AVL 树、二叉树、红黑树、伸展树等——因此我们需要通过挖掘洞穴来准备一些单元格：

• 为了有足够的树木用于每年的树木问题，我们需要至少有 $A$ 个已准备好的单元格。
• 为了妥善照料我们的树木，所有已准备好的单元格集合必须形成一个单一的、与网格对齐的矩形，且该矩形内的每个单元格都必须是已准备好的。

请注意，上述条件也意味着该矩形之外的任何单元格都不能是已准备好的。我们希望果园看起来整洁！

例如，当 $A=11$ 时，虽然下图左侧的 11 个已准备好的单元格形成了一个 $3 \times 4$ 的矩形（即 3 行 4 列），但矩形中心的单元格尚未准备好。因此，我们尚未完成果园的准备工作，因为 $3 \times 4$ 矩形中的每个单元格并非都已准备好。然而，在准备好中心单元格后，大小至少为 11 的矩形就被完全填满了，果园也就准备就绪了。

再看另一个例子。在这种情况下，$A=6$。请注意，中间的图准备了一个 $3 \times 2$ 矩形之外的单元格，因此尽管最右侧的图准备了一个大小为 6 的矩形，但已准备好的单元格的整个集合并没有形成一个矩形（由于左侧多出的单元格）。结果，果园没有准备好。

挖掘对人类来说是艰苦的工作，所以我们从 Google Go 团队借来了 Go 地鼠，并训练它通过准备单元格来帮助我们。我们可以通过给地鼠提供矩阵中一个非边界目标单元格的坐标来部署它。然而，我们还没有完善地鼠的训练，所以它会从以目标单元格为中心的 $3 \times 3$ 九宫格中均匀地（伪）随机选择一个单元格，然后准备它所选择的单元格。（如果它选择了一个已经准备好的单元格，它会徒劳地再次准备它。）

在它感到疲倦无法继续挖掘之前，我们最多只能部署地鼠 1000 次，因此我们需要你的帮助来找出如何战略性地部署它。当你部署地鼠时，你会被告知地鼠实际准备了哪个单元格，如果需要，你可以在再次部署之前将此信息考虑在内。请注意，你不必提前声明矩形的尺寸或位置。

输入格式

这是一个交互式问题，这意味着输入和输出的概念与标准 Code Jam 问题不同。你将与一个单独的进程进行交互，该进程既为你提供信息，又评估你的响应。所有信息都通过标准输入进入你的程序；你需要传达的任何内容都应通过标准输出发送。请记住，许多编程语言默认会对输出进行缓冲，因此在阻塞等待响应之前，请确保你的输出确实已发送（例如，通过刷新缓冲区）。请参阅 FAQ 以了解刷新缓冲区的含义。你的程序通过标准错误发送的任何内容都会被忽略，但它可能会消耗一些内存并计入你的内存限制，因此不要使其溢出。为了帮助你调试，问题陈述的最后提供了本地测试工具脚本（Python 编写）。此外，在 Number Guessing 的分析中提供了之前 Code Jam 交互式问题的示例解决方案（支持所有我们的语言）。

程序首先应读取包含单个整数 $T$ 的单行，表示测试用例的数量。然后，你需要处理 $T$ 个测试用例。

对于每个测试用例，你的程序将读取包含单个整数 $A$ 的单行，表示所需的最小已准备矩形面积。然后，你的程序将与我们的评测机进行最多 1000 次交换。

对于每次交换，你的程序需要使用标准输出发送包含两个整数 $I$ 和 $J$ 的单行：你想要部署地鼠的目标行号和列号。这两个整数必须在 2 到 999 之间，并以十进制书写，且没有前导零。如果你的输出格式错误（例如，值越界），你的程序将失败，评测机将向你发送一行 -1 -1，这表示你的测试已失败，之后它将不会向你的输入流发送任何内容。否则，作为对你部署的响应，评测机将向你的输入流打印包含两个整数 $I'$ 和 $J'$ 的单行，你的程序必须通过标准输入读取它。

如果最后一次部署导致已准备好的单元格集合成为面积至少为 $A$ 的矩形，你将得到 $I' = J' = 0$，这标志着测试用例的结束。否则，$I'$ 和 $J'$ 是地鼠实际准备的单元格的行号和列号，满足 $|I'-I| \le 1$ 且 $|J'-J| \le 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 判决。

请注意，对于给定的测试用例，地鼠从每个 $3 \times 3$ 块中选择的单元格是（伪）随机且相互独立的，但它们在同一个测试用例的每次尝试中都是使用相同的种子确定的，因此对于某个测试用例给出错误结果的解决方案在针对该测试用例的所有尝试中都会一致地给出错误结果。我们也为不同的测试用例设置了不同的种子。

数据范围

$1 \le T \le 20$。 内存限制：1 GB。

测试集 1 (可见)

$A = 20$。 时间限制（整个测试集）：20 秒。

测试集 2 (隐藏)

$A = 200$。 时间限制（整个测试集）：60 秒。

样例

样例输入 1

2
3
10 11
10 10
10 11
11 10
0 0
3
-1 -1

样例输出 1

10 10
10 10
10 12
10 10
11 10
10 10

说明

上述伪代码是针对一个测试集的交互示例的前半部分。假设此测试集中只有两个测试用例。伪代码首先将测试用例的数量读入整数 $t$。然后第一个测试用例开始。对于第一个测试用例，假设 $A$ 为 3（尽管在真实的测试集中，$A$ 总是 20 或 200）。伪代码首先将 $A$ 的值读入整数 $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 = 3$，并决定发送 10 10 进行准备。然而，这一次，代码忘记刷新 stdout 缓冲区！结果，10 10 被缓冲而没有发送给评测机。评测机和代码都在等待对方，导致死锁，最终出现 Time Limit Exceeded 错误。

上面的代码是另一个例子。假设对于第二个测试用例，代码记得刷新输出缓冲区，但发送了 1 1 进行准备。请记住，所选单元格的行和列都必须在范围 $[2, 999]$ 内，所以 1 1 是非法的！结果，评测机发回 -1 -1。然而，在将 -1 -1 读入 $x$ 和 $y$ 后，代码继续向评测机发送另一个单元格位置，并等待。由于输入流中没有内容（评测机已停止发送信息），代码挂起，最终将收到 Time Limit Exceeded 错误。

请注意，如果上述示例中的代码在读取 -1 -1 后立即退出，它将收到 Wrong Answer 判决：

a = readline_int() // reads 3 into a
printline 1 1 to stdout // sends out cell 1 1 to prepare
x, y = readline_two_int() // reads -1 -1, since 1 is outside the range [2, 999]
exit // receives a Wrong Answer judgment

测试工具

你可以使用此测试工具在本地或我们的平台上进行测试。要在本地测试，你需要与你的代码并行运行该工具；你可以使用我们的交互式运行器。有关更多信息，请阅读该文件中的注释，并查看 FAQ 的“交互式问题”部分。

测试工具的说明包含在工具内的注释中。我们鼓励你添加自己的测试用例。

请注意，虽然测试工具旨在模拟评测系统，但它不是真实的评测系统，其行为可能会有所不同。如果你的代码通过了测试工具但在真实的评测机上失败，请检查 FAQ 的“编码”部分，以确保你使用的编译器与我们相同。

[下载测试工具]