A. Bitwise Operation Wizard
bitmasks; constructive algorithms; greedy; interactive; math
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.
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.
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.