CF1934D2 XOR Break — Game Version

这是一个交互题。 这是该问题的游戏版本。请注意，本题的解法与单人版本的解法可能相同，也可能不同。你可以分别独立地解决并获得两种版本的分数。 Alice 和 Bob 正在玩一个游戏。游戏开始时有一个正整数 $n$，两位玩家轮流操作。每一轮，游戏按如下顺序进行： - 当前玩家将整数 $p$ 拆分成两个整数 $p_1$ 和 $p_2$，其中 $0 < p_1 < p$，$0 < p_2 < p$，并且 $p_1 \oplus p_2 = p$。 - 如果不存在这样的 $p_1$ 和 $p_2$，则当前玩家输掉游戏。 - 否则，对手从 $p_1$ 和 $p_2$ 中任选一个整数。 - 游戏继续，对手尝试对被选中的整数进行拆分。 作为 Alice，你的目标是获胜。你最多可以执行 $63$ 次拆分操作。你可以选择先手或后手。系统将为 Bob 操作。 这里的 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每组测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的唯一一行包含一个整数 $n$（$1 \leq n \leq 10^{18}$），即游戏的起始数字。

对于每个测试用例，交互从读取整数 $n$ 开始。 读入 $n$ 后，输出一行，内容为 "first" 或 "second"，表示你选择先手或后手。 在 Alice 的回合，你需要输出两个正整数 $p_1$ 和 $p_2$，满足 $0 < p_1 < p$，$0 < p_2 < p$，且 $p_1 \oplus p_2 = p$。此处 $p$ 等于上一次 Bob 输出的两个整数之一。如果这是第一回合，则 $p = n$。如果 Alice 无法进行拆分操作，输出 "0 0"，你将收到 Wrong answer 判定。 在 Bob 的回合，你需要读入两个整数 $p_1$ 和 $p_2$，满足 $0 < p_1 < p$，$0 < p_2 < p$，且 $p_1 \oplus p_2 = p$。此处 $p$ 等于上一次 Alice 输出的两个整数之一。如果这是第一回合，则 $p = n$。如果 Bob 无法进行拆分操作，则 $p_1 = 0$ 且 $p_2 = 0$，此时你应进入下一个测试用例。 如果 Alice 的拆分操作无效，交互器会输出 "-1 -1"，你的代码应立即退出，否则会收到 Wrong answer 判定。 如果 Alice 已经操作了 $63$ 次，且 Bob 还能对当前整数进行拆分，交互器会输出 "-1 -1"，你的代码应立即退出，否则会收到 Wrong answer 判定。 每次输出后，不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。 本题不支持 Hack。

交互说明示例。 | 交互方 / 玩家 | 操作 | 说明 | |:---|:---|:---| | 4 | $t$ | 测试用例数 | | 1 | $n$ | 第一个测试用例的 $n$ | | second | | Alice 选择后手 | | 0 0 | | Bob 表示无法拆分 $p = 1$ | | 3 | $n$ | 第二个测试用例的 $n$ | | first | | Alice 选择先手 | | 1 2 | | Alice 将 $p = 3$ 拆分为 $p_1 = 1$ 和 $p_2 = 2$ | | 0 0 | | Bob 表示无法拆分 $p = 1$ 或 $p = 2$ | | 13 | $n$ | 第三个测试用例的 $n$ | | first | | Alice 选择先手 | | 10 7 | | Alice 将 $p = 13$ 拆分为 $p_1 = 10$ 和 $p_2 = 7$ | | 3 4 | | Bob 将 $p = 7$ 拆分为 $p_1 = 3$ 和 $p_2 = 4$ | | 1 2 | | Alice 将 $p = 3$ 拆分为 $p_1 = 1$ 和 $p_2 = 2$ | | 0 0 | | Bob 表示无法拆分 $p = 1$ 或 $p = 2$ | | 777777770001 | $n$ | 第四个测试用例的 $n$ | | first | | Alice 选择先手 | | 777777770000 1 | | Alice 将 $p = 777\,777\,770\,001$ 拆分为 $p_1 = 777\,777\,770\,000$ 和 $p_2 = 1$ | | 0 0 | | Bob 表示无法拆分 | 本表仅为说明示例，并不代表交互器的实际行为。 注意，在最后一个测试用例中，Bob 可以选择 $p_1$ 并继续拆分，但他选择了放弃。 由 ChatGPT 4.1 翻译