Description

今年早些时候，Code Jam 团队在一只勤劳的地鼠的帮助下种植了一片果园。可能是它把消息告诉了其他地鼠，现在果园里住着 2 到 25 只地鼠。但我们很难确定具体有多少只，因为这些地鼠只在夜间从地下洞穴出来觅食，而我们经过一天的修剪树木后太累，无法熬夜观察。不过，我们知道每天可以制作一个“地鼠零食”，晚上放出去看看是否被吃掉。我们认为可以利用这些信息来确定地鼠的数量。

以下是我们已知的地鼠觅食方式。$N$ 只地鼠会在白天开会，决定接下来 $N$ 个夜晚它们出洞的顺序，每晚一只。然后，在接下来的第 $i$ 个夜晚，顺序中的第 $i$ 只地鼠会出来寻找地鼠零食。每只地鼠都有自己独特的口味等级（且永远不会改变），只有当零食的质量等级不低于该地鼠的口味等级时，它才会吃掉零食。在顺序中的第 $N$ 只地鼠出来后的第二天，地鼠们会重新决定顺序，流程再次循环。注意，即使某只地鼠选择不吃它发现的零食，它也不会再次出现，直到下次会议决定的新顺序轮到它。

我们每天必须制作一个新的地鼠零食；即使零食没有被吃掉，也会变质，不能留到第二天。每天早上，我们会得知前一晚的零食是否被吃掉。

今天，我们知道地鼠们正在开会决定新的顺序，所以今晚将是新顺序的开始。我们愿意为这项调查投入大量时间——最多 $10^5$ 个夜晚。请你帮我们用不超过 $S$ 个零食，确定地鼠的数量。

交互协议

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

最开始，你的程序应读取一行，包含一个整数 $T$，表示测试用例数量。然后，你需要处理 $T$ 个测试用例。对于每个测试用例，你的程序首先读取一行，包含一个整数 $S$，表示你最多可以使用的零食数量。接下来，你的程序将与评测机进行最多 $S+1$ 次交互，其中最后一次必须是对答案的猜测。

在第 $i$ 次交互中，你的程序需要通过标准输出发送一行，包含一个整数 $Q_i$。

• 如果 $Q_i$ 在区间 $[1, 10^6]$ 内，表示你放置了一个质量等级为 $Q_i$ 的地鼠零食。作为回应，评测机会向你的输入流输出一行，包含一个整数：若地鼠吃了零食则为 1，否则为 0。你的程序必须通过标准输入读取该值。然后可以开始下一次交互。
• 如果 $Q_i$ 在区间 $[-25, -2]$ 内，表示你认为本测试用例中有 $-Q_i$ 只地鼠。如果你的答案正确，评测机会进入下一个测试用例（如果还有的话）。

如果发生以下任一情况，评测机会输出一行 $-1$，然后停止向你的输入流发送输出：

1. 你的程序发送了格式错误或越界的值（如 $1000001$、$-1$ 或 GO_IS_THE_BEST_LANGUAGE），或发送了过多的值（如 1 2）。
2. 在当前测试用例中，已经发送了 $S$ 个值后，又发送了区间 $[-25, -2]$ 内的值。
3. 你的程序发送了区间 $[-25, -2]$ 内的值，但答案不正确。注意，每个测试用例你只有一次答题机会。

如果你的程序在收到 $-1$ 后仍继续等待评测机，将会超时，导致 Time Limit Exceeded 错误。请注意，你有责任让程序及时退出，以获得正确的评判结果（Wrong Answer、Runtime Error 等），而不是超时。和往常一样，如果总时间或内存超限，或程序运行时出错，你将收到相应的评判结果。

在解决所有测试用例后，不应再向评测机发送任何信息。换句话说，如果你在发送最后一个测试用例的答案后仍继续向标准输出打印内容，将会被判为 Wrong Answer。

Input Format

见交互协议。

Output Format

见交互协议。

Hint

样例交互

以下交互为测试集 1 的示例。

  // 在本例中，出题人已确定第一个测试用例有两只地鼠，口味等级分别为 1 和 2（我们称它们为 A 和 B），第二个测试用例有四只地鼠，口味等级分别为 1、999、123 和 4567（我们称它们为 C、D、E 和 F）。
  // 评测机随机生成第一个顺序：A, B。
  t = readline_int()           // 代码读取到 t=2。
  s = readline_int()           // 代码读取到 s=100000。
  printline 1 to stdout        // 代码发送一个质量等级为 1 的零食。
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 A 吃了零食）。
  printline 1 to stdout
  flush stdout
  resp = readline_srt()        // 代码读取到 resp=0（地鼠 B 没有吃零食）。
                               // 评测机随机生成下一个顺序 B, A。
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 B 吃了零食）。
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 A 吃了零食）。
                               // 评测机随机生成下一个顺序 B, A。
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 B 吃了零食）。
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 A 吃了零食）。
  printline -2 to stdout       // 代码正确判断唯一符合条件的情况是两只地鼠，口味等级为 1 和 2。
  flush stdout                 // 评测机判定答案正确，准备下一个测试用例……
                               // 评测机随机生成 C, E, F, D 作为第一个顺序。
  s = readline_int()           // 代码读取到 s=100000。（这也说明第一个测试用例答案正确。）
  printline 0 to stdout        // 代码发送了一个非法值。
  flush stdout
  resp = readline_str()        // 代码读取到 resp=-1。
  exit                         // 代码退出以避免出现不明确的 TLE 错误。

以下交互为测试集 2 的示例。注意第一个测试用例的交互与前例相同，但结果不同。

  // 在本例中，出题人已确定第一个测试用例有三只地鼠，口味等级分别为 1、2 和 1；我们称它们为 A、B 和 C，顺序为 ABCCBAABCCBA……
  t = readline_int()           // 代码读取到 t=1。
  s = readline_int()           // 代码读取到 s=100000。
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 A 吃了零食）。
  printline 1 to stdout
  flush stdout
  resp = readline_srt()        // 代码读取到 resp=0（地鼠 B 没有吃零食）。
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 C 吃了零食）。
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 C 吃了零食）。
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // 代码读取到 resp=1（地鼠 B 吃了零食）。
  printline -2 to stdout       // 代码错误地判断只有两只地鼠 A 和 B，口味等级为 1 和 2；这与当前顺序 A,B,A,B,A 一致，但实际地鼠数量不同，因此评测机判定错误。
  flush stdout
  s = readline_str()           // 代码尝试读取 s，但得到 -1，表示上一个测试用例答案错误。
  exit                         // 代码退出以避免出现不明确的 TLE 错误。

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

测试工具的使用说明已包含在工具注释中。我们鼓励你自行添加测试用例。请注意，尽管测试工具旨在模拟评测系统，但它不是真实的评测系统，可能会有不同的行为。

重要警告

你与评测机之间的上下文切换开销很大，在我们的评测系统中更甚。与其他交互题不同，我们发现本题所有参考解法都需要将多次交互打包发送。即，不是“打印口味等级，读取响应，打印口味等级，读取响应”，而是“打印多个口味等级，再读取多个响应”，这样可以减少上下文切换。

性能基准

为帮助你了解不同批量交互的性能，我们提供了如下基准。我们写了一个程序，进行 $S=10^5$ 次交互，每 $B$ 次为一组——即先打印 $B$ 个口味等级，再读取 $B$ 个响应，如此 $S/B$ 组。我们用 Python 和 C++ 实现，始终将 $B$ 个口味等级打印到字符串变量，最后再输出，确保批量内不刷新缓冲区。以下为每个批量大小 $B$ 的耗时（秒，向上取整，多次运行取最大值）：

注意，批量较小时，上下文切换时间可降至每组 5 秒以内，整个测试集不到一分钟。

数据范围

• $1 \leq T \leq 10$。
• 地鼠数量在 2 到 25 之间，口味等级在 1 到 $10^6$ 之间。$S=10^5$。

测试集 1（10 分，可见）

• 没有两只地鼠的口味等级相同。
• 每晚地鼠出洞顺序均匀随机，从所有可能顺序中独立选择。

测试集 2（38 分，隐藏）

• 集合 $\{x : \text{存在恰好 } x \geq 1 \text{ 只地鼠口味等级相同}\}$ 的最大公约数为 1。
• 地鼠出洞顺序与所提供零食无关，且每次独立选择。

对于每个测试用例，口味等级的多重集和随机数生成种子由出题人在赛前预先生成，对于任何选手、任何提交都是相同的。这意味着对于同一个测试用例，提交相同数量 $s_i$ 的零食，地鼠出现的顺序也完全相同。

• 例如，以下情况在任意测试集都可能出现：
  • 两只地鼠，口味等级分别为 1 和 2
• 以下情况只可能出现在测试集 2，不会出现在测试集 1：
  • 三只地鼠，两只口味等级为 1，一只口味等级为 2
• 以下情况在任意测试集都不会出现：
  • 六只地鼠，四只口味等级为 1，两只口味等级为 2
  • 两只地鼠，口味等级均为 7

由 ChatGPT 4.1 翻译