这是一个交互问题。
奥克斯弗特学院超自然现象学部开放了魔法图书馆,里面藏有瑞达尼亚最伟大巫师的作品——$$$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”(错误答案)的判决。
输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到“IL”(超出空闲限制)的判决。要刷新缓冲区,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要进行破解,请使用以下格式。
第一行应包含一个整数 $$$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$$$ 必须不同。
示例
输入 #1
2 6 0 2 3 5 3
输出 #1
xor 1 1 xor 2 2 xor 3 3 xor 4 6 ans 2 3 5 ans 1 2 3
注意
在第一个测试用例中,被盗后图书馆中的书籍如下所示:
现在考虑问题的答案:
- 对于查询“xor 1 1”,您将收到结果 $$$1 \oplus 1 = 0$$$。两本书籍满足查询中指定的条件 — 编号均为 $$$1$$$。
- 对于查询“xor 2 2”,您会收到结果 $$$2$$$,因为只有一本书满足指定条件。
- 对于查询“xor 3 3”,您将收到结果 $$$3$$$。
- 对于查询“xor 4 6”,您将收到结果 $$$4 \oplus 6 \oplus 4 \oplus 5 \oplus 6 = 5$$$。
在第二个测试用例中,只有 $$$3$$$ 类型的书籍,很容易猜测缺少的书籍的编号为 $$$1$$$、$$$2$$$ 和 $$$3$$$。