Description

Zillionim 是一个由两名玩家轮流进行的回合制游戏。最初，$10^{12}$ 枚硬币首尾相连排成一行，从左到右编号为 $1$ 到 $10^{12}$。每一回合，玩家必须选择 $10^{10}$ 枚连续的硬币并将其移除。即使中间的硬币被移除，原本不相邻的两枚硬币也不会变得相邻。

在自己的回合，玩家如果可以，则必须进行一次合法操作，然后轮到对手。如果某位玩家在自己的回合无法进行合法操作，则该玩家输掉本局游戏（对手获胜）。

由于我们的工程师仍在努力训练我们的机器学习模型来玩 Zillionim，我们为 Zillionim 创建了一个简单的 AI，它会随机进行操作。AI 总是先手。在每次 AI 的回合，AI 会确定所有合法操作，并从中均匀随机选择一个。

你能击败这个 AI 吗……至少大多数时候？

交互协议

本题为交互题。

最开始，你的程序应读取一行包含两个整数 $\mathbf{T}$（测试用例数量）和 $\mathbf{W}$（你的解答被判为正确所需赢下的最少局数）。然后，你需要处理 $\mathbf{T}$ 个测试用例，每个用例即为一局 Zillionim 游戏。

每个测试用例通过与评测器的多轮交互进行，直到某一方获胜。每轮交互中，评测器首先输出一行，内容为一个整数 $\mathbf{P}$，含义如下：

• 如果 $1 \leq \mathbf{P} \leq 10^{12} - 10^{10} + 1$，则表示 AI 移除了编号为 $\mathbf{P}$ 到 $\mathbf{P} + 10^{10} - 1$ 的硬币，现在轮到你。注意，这意味着你至少还有一个合法操作可以进行。AI 总是会进行合法操作。
• 如果 $\mathbf{P} = -2$，表示你上一次操作后赢得了本局游戏。
• 如果 $\mathbf{P} = -3$，表示 AI 上一次操作后赢得了本局游戏。注意此时评测器不会告知你 AI 的最后一步操作。
• 如果 $\mathbf{P} = -1$，表示你上一次发送给评测器的信息有误（数据格式错误、操作越界或试图移除已被移除的硬币），你将因未正确操作而被判为 Wrong Answer（见下文）。

在收到正整数 $\mathbf{P}$ 后，你应输出一行，内容为正整数 $\mathbf{Q}$（$1 \leq \mathbf{Q} \leq 10^{12} - 10^{10} + 1$），表示你要移除编号为 $\mathbf{Q}$ 到 $\mathbf{Q} + 10^{10} - 1$ 的硬币。你移除的这些硬币必须在当前局中尚未被移除。

当评测器发送 $-2$ 或 $-3$ 后，如果这是最后一局，评测器会终止，你的程序也应随之终止。否则，评测器会继续发送下一局的首轮数据。在所有局都正确处理完毕前，评测器不会检查你赢了多少局。例如，如果你赢了 $\mathbf{T} - 1$ 局，但在最后一局发送了错误数据，你将被判为 Wrong Answer，无论 $\mathbf{W}$ 的值是多少。

收到 $-1$ 后，你的程序应立即终止以获得 Wrong Answer 判定。如果收到 $-1$ 后仍继续等待评测器数据，你的程序将因超时被判为 Time Limit Exceeded。请注意，程序应自行正常退出，以获得 Wrong Answer 而不是 Runtime Error 或 Time Limit Exceeded。

每一局的随机数种子是预先设定且互不相同的。这意味着，如果两份提交在同一局中做出完全相同的操作序列，将收到 AI 完全相同的操作序列。AI 在一局中的操作不会受到同一测试集内前几局操作的影响（即伪随机生成器的状态是独立的）。

Input Format

见交互协议。

Output Format

见交互协议。

Hint

交互样例

为简化说明，以下交互样例假设总共有 $50$ 枚硬币，每次移除 $10$ 枚连续硬币，其余规则与原题一致。

  t, w = readline_int_list()   // 读取 t=500, w=300
  p = readline_int()           // 读取 p=23，表示第一局 AI 移除了 23~32 号硬币
  printline 38 to stdout       // 我们选择移除 38~47 号硬币
  flush stdout
  p = readline_int()           // 读取 p=3，AI 移除了 3~12 号硬币
  printline 13 to stdout       // 我们选择移除 13~22 号硬币（这是我们唯一剩下的合法操作）
  flush stdout
  p = readline_int()           // 读取 p=-2，表示我们赢了第一局
  p = readline_int()           // 读取 p=32，第二局开始，AI 移除了 32~41 号硬币
  printline 13 to stdout       // 我们选择移除 13~22 号硬币
  flush stdout
  p = readline_int()           // 读取 p=-3，AI 获胜，我们无法操作
  p = readline_int()           // 读取 p=10，第三局开始，AI 移除了 10~19 号硬币
  printline 0 to stdout        // 我们选择了非法下标（硬币编号从 1 开始！）
  flush stdout
  p = readline_int()           // 读取 p=-1，表示我们操作有误
  exit                         // 立即退出，避免超时

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

测试工具的使用说明已包含在工具文件的注释中。我们鼓励你自行添加测试用例。请注意，测试工具旨在模拟评测系统，但并非真实评测系统，可能存在行为差异。

数据范围

• $\mathbf{T} = 500$。
• $-3 \leq \mathbf{P} \leq 10^{12} - 10^{10} + 1$。
• $\mathbf{P} \neq 0$。
• $\mathbf{P}$ 表示一次合法操作或游戏状态信息，详见上文。

测试点 1（1 分，公开）

• $\mathbf{W} = 300$。

测试点 2（5 分，公开）

• $\mathbf{W} = 475$。

测试点 3（6 分，公开）

• $\mathbf{W} = 499$。

由 ChatGPT 4.1 翻译