1936A · Bitwise Operation Wizard

Problem: 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 Format: 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.

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.