CF1936A.Bitwise Operation Wizard

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 \lt 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 \lt y$, $x \gt y$, or $x = y$.

Please find any two indices $i$ and $j$ ($0 \le i,j \lt 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.

这是一个交互式问题。

存在一个秘密序列 $p_0, p_1, \ldots, p_{n-1}$，它是集合 $\{0,1,\ldots,n-1\}$ 的一个排列。

你需要找出任意两个下标 $i$ 和 $j$，使得 $p_i \oplus p_j$ 达到最大值，其中 $\oplus$ 表示按位异或运算。

为此，你可以提出查询。每次查询的形式如下：你任选四个下标 $a$、$b$、$c$、$d$（满足 $0 \le a,b,c,d \lt n$）。随后，评测系统计算 $x = (p_a \mid p_b)$ 和 $y = (p_c \mid p_d)$，其中 $|$ 表示按位或运算。最后，你会收到 $x$ 与 $y$ 的比较结果，即被告知 $x \lt y$、$x \gt y$ 或 $x = y$ 中的哪一种情况。

请在至多 $3n$ 次查询内，找出任意一对下标 $i$ 和 $j$（满足 $0 \le i,j \lt n$），使得 $p_i \oplus p_j$ 在所有可能的下标对中取到最大值。若存在多个满足条件的下标对，输出其中任意一对即可。

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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是测试用例的描述。

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 \lt (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 \gt (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,3,1,2]$。

对于查询 "? 0 2 3 1"，评测系统返回 "<"，因为 $(p_0 \mid p_2) = (0 \mid 1) =1 \lt (p_3 \mid p_1) = (2 \mid 3) = 3$。

对于查询 "? 1 1 2 3"，评测系统返回 "="，因为 $(p_1 \mid p_1) = (3\mid 3)= 3 = (p_2 \mid p_3) = (1 \mid 2)=3$。

对于查询 "? 1 2 0 3"，评测系统返回 ">"，因为 $(p_1 \mid p_2) = (3 \mid 1) = 3 \gt (p_0 \mid p_3) = (0\mid 2)=2$。

答案 $i = 3$ 和 $j = 2$ 是合法的：$(p_3 \oplus p_2) = (2 \oplus 1) = 3$ 确实等于 $p_i \oplus p_j$ 的最大可能值。另一组合法答案为 $i=0$ 和 $j=1$。由于查询次数不超过 $3n=12$，该答案被视为正确。

在第二个测试用例中，$n = 2$，因此 $p$ 要么是 $[0, 1]$，要么是 $[1, 0]$。无论哪种情况，$p_0 \oplus p_1 = 1$ 均为最大可能值。