这是一个交互问题。
有两个隐藏整数 $$$k$$$ 和 $$$c$$$ 使得 $$$k\in \{1,2,3\}$$$ 和 $$$1\le c\le 2^n-1$$$。 请注意 $$$c\neq 0$$$。
在进行任何互动之前,您需要告诉陪审团 非负 整数$$$a\le 2^n-1$$$。然后,评分者将使用 $$$a$$$ 作为集合 $$$S$$$ 中的初始元素,即最初 $$$S = \{a\}$$$。
接下来,您最多可以进行以下两种类型的 $$$n+3$$$ 查询:
- 选择一个整数 $$$x$$$,使得 $$$0\leq x\le 2^n-1$$$。陪审团会将 $$$f(x)$$$ 插入 $$$S$$$ 中,然后以 $$$|S|$$$ 响应(即插入后 $$$S$$$ 的大小);
- 选择一个整数 $$$y$$$,使得 $$$0\leq y\le 2^n-1$$$。陪审团将回答整数 $$$z$$$ 的数量,使得 $$$z\in S$$$ 和 $$$z\geq y$$$。
$$$f(x)$$$ 的定义如下:
$$f(x)= \begin{cases} x\,\&\,c & \text{if}\, k=1,\\ x\,|\,c & \text{if}\, k=2,\\ x\oplus c & \text{if}\, k=3.\\ \end{cases}$$
这里,$$$\&$$$表示按位与运算,$$$|$$$表示按位或运算,$$$\oplus$$$表示按位异或运算。
您的任务是使用最多 $$$n+3$$$ 交互来确定 $$$k$$$ 和 $$$c$$$ 的值。
请注意,报告答案不计入 $$$n+3$$$ 互动。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 60$$$)。然后,进行互动。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
互动
首先,您需要输出一个整数 $$$a$$$ ($$$0\leq a\le 2^n-1$$$) — 您为集合 $$$S$$$ 选择的初始元素。
要进行交互,请按以下格式输出一行:
- $$$\mathtt{I}\;x$$$ ($$$0\leq x\le 2^n-1$$$) — 将 $$$f(x)$$$ 插入集合 $$$S$$$ 中。之后,评审团将返回$$$|S|$$$。
- $$$\mathtt{Q}\;y$$$ ($$$0\leq y\le 2^n-1$$$) — 查询集合 $$$S$$$ 中有多少个 $$$z$$$-s 满足 $$$z \geq y$$$。陪审团将返回此类 $$$z$$$-s 的计数。
要给出最终答案,请按以下格式输出一行:
- $$$\mathtt{A}\;k\;c$$$ ($$$1\leq k\le 3$$$, $$$1\leq c\le 2^n-1$$$) — $$$k$$$ 和 $$$c$$$ 的值。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
请注意,评分者是 非自适应。这意味着 $$$k$$$ 和 $$$c$$$ 的值在开始时是固定的,不会根据您的交互而改变。
黑客
要破解,请使用以下格式。
第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行应包含三个整数 $$$n$$$、$$$k$$$ 和 $$$c$$$ ($$$2 \leq n \leq 60$$$、$$$1\leq k\le 3$$$、$$$1\leq c\le 2^n-1$$$)。
所有测试用例的 $$$n$$$ 总和不应超过 $$$10^5$$$。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
3 2 1 2 2 1 2 2 3 2 2 2 2
输出复制
3 I 3 A 1 3 1 I 0 Q 2 Q 1 Q 0 I 3 A 2 2 1 I 1 I 0 A 3 1
注意
示例中的交互过程如下:
| 解决方案 | 评审团 | 说明 |
| 3 | 有 $$$3$$$ 测试用例。 | |
| 2 | $$$n=2$$$。隐藏的整数值为 $$$k=1$$$ 和 $$$c=3$$$。 | |
| 3 | 最初,$$$S = \{3\}$$$。 | |
| 我 3 | 1 | 将 $$$f(3)=3\,\& \,3=3$$$ 插入 $$$S$$$ 中。那么$$$S=\{3\}$$$,所以响应是$$$|S|=1$$$。 请注意,集合 $$$S$$$ 中的元素不允许重复。 |
| A 1 3 | 该解决方案的结论是 $$$k=1$$$ 和 $$$c=3$$$。 | |
| 2 | $$$n=2$$$。隐藏的整数值为 $$$k=2$$$ 和 $$$c=2$$$。 | |
| 1 | 最初,$$$S = \{1\}$$$。 | |
| 我0 | 2 | 将 $$$f(0)=0\,|\,2=2$$$ 插入 $$$S$$$ 中。那么$$$S=\{1,2\}$$$,所以响应是$$$|S|=2$$$。 |
| 问题2 | 1 | 当$$$z$$$为$$$2$$$时,满足$$$z\in S$$$和$$$z\geq 2$$$,因此响应为$$$1$$$。 |
| 问题1 | 2 | 当$$$z$$$为$$$1$$$或$$$2$$$时,满足$$$z\in S$$$和$$$z\geq 1$$$,因此响应为$$$2$$$。 |
| 问0 | 2 | 当$$$z$$$为$$$1$$$或$$$2$$$时,满足$$$z\in S$$$和$$$z\geq 0$$$,因此响应为$$$2$$$。 |
| 我 3 | 3 | 将 $$$f(3)=3\,|\,2=3$$$ 插入 $$$S$$$ 中。那么$$$S=\{1,2,3\}$$$,所以响应是$$$|S|=3$$$。 |
| A 2 2 | 该解决方案的结论是 $$$k=2$$$ 和 $$$c=2$$$。 | |
| 2 | $$$n=2$$$。隐藏的整数值为 $$$k=3$$$ 和 $$$c=1$$$。 | |
| 1 | 最初,$$$S = \{1\}$$$。 | |
| 我 1 | 2 | 将 $$$f(1)=1\oplus 1=0$$$ 插入 $$$S$$$ 中。那么$$$S=\{0,1\}$$$,所以响应是$$$|S|=2$$$。 |
| 我0 | 2 | 将 $$$f(1)=0\oplus 1=1$$$ 插入 $$$S$$$ 中。那么$$$S=\{0,1\}$$$,所以响应是$$$|S|=2$$$。 请注意,集合 $$$S$$$ 中的元素不允许重复。 |
| A 3 1 | 该解决方案的结论是 $$$k=3$$$ 和 $$$c=1$$$。 |
示例输入和输出中的空行只是为了更好的可读性;您不需要在解决方案中输出它们。
请注意,在示例中,给定的查询实际上不足以唯一地确定值;它们仅用于说明输入/输出格式。