← Home
write a go solution for Description:
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_ioplusp_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<=a,b,c,d<n). Next, the jury calculates x=(p_amidp_b) and y=(p_cmidp_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<=i,j<n) such that p_ioplusp_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<=t<=10^3). The description of the test cases follows.

Output Format:
None

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_0midp_2)=(0mid1)=1<(p_3midp_1)=(2mid3)=3.

For the query "? 1 1 2 3", the jury return "=" because (p_1midp_1)=(3mid3)=3=(p_2midp_3)=(1mid2)=3.

For the query "? 1 2 0 3", the jury return ">" because (p_1midp_2)=(3mid1)=3>(p_0midp_3)=(0mid2)=2.

The answer i=3 and j=2 is valid: (p_3oplusp_2)=(2oplus1)=3 is indeed equal to the maximum possible value of p_ioplusp_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_0oplusp_1=1 is maximum possible.. Output only the code with no comments, explanation, or additional text.