CF2036G.Library of Magic

这是一个交互题。

奥森福特学院的超自然现象系开启了魔法图书馆，馆内收藏了雷达尼亚最伟大的巫师们的著作——共 $n$ 种类型的书籍（$3 \leq n \leq 10^{18}$），编号从 $1$ 到 $n$。每本书的类型编号都标在书脊上。此外，每种类型的书在图书馆中恰好有两本！而你被任命为图书管理员。

某天夜里，你被奇怪的声音惊醒，看到一个生物正从窗户离开。你注意到神秘小偷的背包里露出了三本颜色各异的厚重书籍。在你开始寻找它们之前，你决定计算出这些书脊上写着的数字 $a$、$b$ 和 $c$。这三个数字互不相同。

因此，你现在面对的是一组无序的书籍集合，其中包含编号为 $a$、$b$、$c$ 的书各一本，其余编号 $1$ 到 $n$ 中除了 $a$、$b$、$c$ 以外的每个编号的书各有两本。你需要找出这三个值 $a$、$b$、$c$。

由于你所在的不是普通图书馆，而是魔法图书馆，你只能使用一种查询魔法来检查书籍是否在原位：

• “xor l r”——按位异或查询，参数为 $l$ 和 $r$。设 $k$ 为图书馆中编号大于等于 $l$ 且小于等于 $r$ 的书的数量。你将会得到 $v_1 \oplus v_2 \oplus ... \oplus v_k$ 的结果，其中 $v_1 ... v_k$ 是这些书脊上的编号，$\oplus$ 表示按位异或运算。

由于你的魔法能力有限，你最多只能进行 $150$ 次查询。

第一行输入一个整数 $t$（$1 \le t \le 300$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 10^{18}$），表示图书的类型数。

每个测试用例的交互从读取整数 $n$ 开始。

然后你可以进行最多 $150$ 次查询。

每次查询，输出格式为 "xor l r"（不带引号），其中 $1 \leq l \leq r \leq n$。每次查询后，读取一个整数，表示该查询的结果。

当你确定答案后，输出 "ans a b c"（不带引号），其中 $a$、$b$、$c$ 是你找到的答案，可以任意顺序输出。

交互器是非自适应的，即答案在你进行查询前就已确定，不会根据你的查询改变。

如果你进行了 $150$ 次查询后，再进行任何查询，返回的答案将为 $-1$。收到该答案后应立即终止程序，否则会收到“WA”（Wrong Answer）判定。

每次输出查询后，记得输出换行并刷新输出缓冲区，否则会收到“IL”（Idleness limit exceeded）判定。刷新缓冲区的方法如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请参考相关文档。

Hack 格式

如需制作 Hack，使用如下格式：

第一行输入一个整数 $t$（$1 \leq t \leq 300$），表示测试用例数量。

每个测试用例一行，包含四个整数 $n$、$a$、$b$、$c$（$3 \leq n \leq 10^{18}$，$1 \le a, b, c \le n$），分别表示图书类型数和被盗书籍的编号。$a$、$b$、$c$ 必须互不相同。

在第一个测试用例中，失窃后的图书馆书籍情况如下：

现在考虑以下查询的答案：

• 对于查询 "xor 1 1"，你会得到 $1 \oplus 1 = 0$。有两本编号为 $1$ 的书满足条件。
• 对于查询 "xor 2 2"，你会得到 $2$，因为只有一本编号为 $2$ 的书满足条件。
• 对于查询 "xor 3 3"，你会得到 $3$。
• 对于查询 "xor 4 6"，你会得到 $4 \oplus 6 \oplus 4 \oplus 5 \oplus 6 = 5$。

在第二个测试用例中，只有 $3$ 种类型的书，很容易猜出缺失的编号为 $1$、$2$ 和 $3$。

由 ChatGPT 4.1 翻译