311120: CF1937C. Bitwise Operation Wizard

C. Bitwise Operation Wizardtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

There is a secret sequence $p_0, p_1, \ldots, p_{n-1}$, which is a permutation of $\{0,1,\ldots,n-1\}$.

You need to find any two indices $i$ and $j$ such that $p_i \oplus p_j$ is maximized, where $\oplus$ denotes the bitwise XOR operation.

To do this, you can ask queries. Each query has the following form: you pick arbitrary indices $a$, $b$, $c$, and $d$ ($0 \le a,b,c,d < n$). Next, the jury calculates $x = (p_a \mid p_b)$ and $y = (p_c \mid p_d)$, where $|$ denotes the bitwise OR operation. Finally, you receive the result of comparison between $x$ and $y$. In other words, you are told if $x < y$, $x > y$, or $x = y$.

Please find any two indices $i$ and $j$ ($0 \le i,j < n$) such that $p_i \oplus p_j$ is maximum among all such pairs, using at most $3n$ queries. If there are multiple pairs of indices satisfying the condition, you may output any one of them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

Interaction

The first line of each test case contains one integer $n$ ($2 \le n \le 10^4$). At this moment, the permutation $p_0, p_1, \ldots, p_{n-1}$ is chosen. The interactor in this task is not adaptive. In other words, the sequence $p$ is fixed in every test case and does not change during the interaction.

To ask a query, you need to pick four indices $a$, $b$, $c$, and $d$ ($0 \le a,b,c,d < n$) and print the line of the following form:

• "? a b c d"

After that, you receive:

• "<" if $(p_a \mid p_b) < (p_c \mid p_d)$;
• "=" if $(p_a \mid p_b) = (p_c \mid p_d)$;
• ">" if $(p_a \mid p_b) > (p_c \mid p_d)$.

You can make at most $3n$ queries of this form.

Next, if your program has found a pair of indices $i$ and $j$ ($0 \le i, j < n$) such that $p_i \oplus p_j$ is maximized, print the line of the following form:

• "! i j"

Note that this line is not considered a query and is not taken into account when counting the number of queries asked.

After this, proceed to the next test case.

If you make more than $3n$ queries during an interaction, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query or the answer for a test case, do not forget to output the end of line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

Hacks

To hack, follow the test format below.

The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le 10^4$).

The second line of each test case contains $n$ integers $p_0,p_1,\ldots,p_{n-1}$, which represent a permutation of integers from $0$ to $n - 1$.

The sum of $n$ over all test cases should not exceed $10^4$.

ExampleInput

2
4

<

=

>

2

Output

? 0 2 3 1

? 1 1 2 3

? 1 2 0 3

! 3 2

! 0 1

Note

In the first test case, the hidden permutation is $p=[0,3,1,2]$.

For the query "? 0 2 3 1", the jury return "<" because $(p_0 \mid p_2) = (0 \mid 1) =1 < (p_3 \mid p_1) = (2 \mid 3) = 3$.

For the query "? 1 1 2 3", the jury return "=" because $(p_1 \mid p_1) = (3\mid 3)= 3 = (p_2 \mid p_3) = (1 \mid 2)=3$.

For the query "? 1 2 0 3", the jury return ">" because $(p_1 \mid p_2) = (3 \mid 1) = 3 > (p_0 \mid p_3) = (0\mid 2)=2$.

The answer $i = 3$ and $j = 2$ is valid: $(p_3 \oplus p_2) = (2 \oplus 1) = 3$ is indeed equal to the maximum possible value of $p_i \oplus p_j$. Another valid answer would be $i=0$ and $j=1$. As the number of queries does not exceed $3n=12$, the answer is considered correct.

In the second test case, $n = 2$, so $p$ is either $[0, 1]$ or $[1, 0]$. In any case, $p_0 \oplus p_1 = 1$ is maximum possible.

题目大意：这是一个交互式问题。有一个秘密序列 p_0, p_1, ..., p_{n-1}，它是 \{0,1,...,n-1\} 的一个排列。你需要找到任意两个索引 i 和 j，使得 p_i \oplus p_j 最大，其中 \oplus 表示按位异或操作。为了做到这一点，你可以提出查询。每个查询的形式如下：你任意选择索引 a, b, c, 和 d (0 \le a,b,c,d < n)。接下来，评委会计算 x = (p_a | p_b) 和 y = (p_c | p_d)，其中 | 表示按位或操作。最后，你接收到 x 和 y 比较的结果。换句话说，你会被告知 x < y，x > y，还是 x = y。请使用不超过 3n 查询找到使 p_i \oplus p_j 最大的任意两个索引 i 和 j (0 \le i,j < n)。如果有多个满足条件的索引对，你可以输出其中任何一个。

输入输出数据格式：每个测试包含多个测试用例。第一行包含测试用例数 t (1 \le t \le 10^3)。接下来是测试用例的描述。交互的第一行每个测试用例包含一个整数 n (2 \le n \le 10^4)。此时，选择了排列 p_0, p_1, ..., p_{n-1}。在任务中的交互器不是自适应的。换句话说，序列 p 在每个测试用例中是固定的，并且在交互过程中不会改变。要提出查询，你需要选择四个索引 a, b, c, 和 d (0 \le a,b,c,d < n) 并打印以下形式的行：“? a b c d”。之后，你会收到：(p_a | p_b) < (p_c | p_d) 时返回 “<”，(p_a | p_b) = (p_c | p_d) 时返回 “=”，(p_a | p_b) > (p_c | p_d) 时返回 “>”。你可以提出最多 3n 个此类查询。如果你的程序找到了一对索引 i 和 j (0 \le i, j < n) 使得 p_i \oplus p_j 最大，打印以下形式的行：“! i j”。注意，这行不是查询，并且在不计算查询次数时被视为不计入。之后，继续下一个测试用例。如果你在交互中提出超过 3n 个查询，你的程序必须立即终止，并且你将收到 “错误答案” 判决。否则，你可以得到任意判决，因为你的解决方案将继续从已关闭的流中读取。在打印查询或测试用例的答案后，不要忘记输出行尾并刷新输出。否则，你将得到 “空闲超时” 判决。题目大意：这是一个交互式问题。有一个秘密序列 p_0, p_1, ..., p_{n-1}，它是 \{0,1,...,n-1\} 的一个排列。你需要找到任意两个索引 i 和 j，使得 p_i \oplus p_j 最大，其中 \oplus 表示按位异或操作。为了做到这一点，你可以提出查询。每个查询的形式如下：你任意选择索引 a, b, c, 和 d (0 \le a,b,c,d < n)。接下来，评委会计算 x = (p_a | p_b) 和 y = (p_c | p_d)，其中 | 表示按位或操作。最后，你接收到 x 和 y 比较的结果。换句话说，你会被告知 x < y，x > y，还是 x = y。请使用不超过 3n 查询找到使 p_i \oplus p_j 最大的任意两个索引 i 和 j (0 \le i,j < n)。如果有多个满足条件的索引对，你可以输出其中任何一个。 输入输出数据格式：每个测试包含多个测试用例。第一行包含测试用例数 t (1 \le t \le 10^3)。接下来是测试用例的描述。交互的第一行每个测试用例包含一个整数 n (2 \le n \le 10^4)。此时，选择了排列 p_0, p_1, ..., p_{n-1}。在任务中的交互器不是自适应的。换句话说，序列 p 在每个测试用例中是固定的，并且在交互过程中不会改变。要提出查询，你需要选择四个索引 a, b, c, 和 d (0 \le a,b,c,d < n) 并打印以下形式的行：“? a b c d”。之后，你会收到：(p_a | p_b) < (p_c | p_d) 时返回 “<”，(p_a | p_b) = (p_c | p_d) 时返回 “=”，(p_a | p_b) > (p_c | p_d) 时返回 “>”。你可以提出最多 3n 个此类查询。如果你的程序找到了一对索引 i 和 j (0 \le i, j < n) 使得 p_i \oplus p_j 最大，打印以下形式的行：“! i j”。注意，这行不是查询，并且在不计算查询次数时被视为不计入。之后，继续下一个测试用例。如果你在交互中提出超过 3n 个查询，你的程序必须立即终止，并且你将收到 “错误答案” 判决。否则，你可以得到任意判决，因为你的解决方案将继续从已关闭的流中读取。在打印查询或测试用例的答案后，不要忘记输出行尾并刷新输出。否则，你将得到 “空闲超时” 判决。