Description:
This is an interactive problem.
There is a secret permutation $$$p$$$ ($$$1$$$-indexed) of numbers from $$$1$$$ to $$$n$$$. More formally, for $$$1 \leq i \leq n$$$, $$$1 \leq p[i] \leq n$$$ and for $$$1 \leq i < j \leq n$$$, $$$p[i] \neq p[j]$$$. It is known that $$$p[1]<p[2]$$$.
In $$$1$$$ query, you give $$$3$$$ distinct integers $$$a,b,c$$$ ($$$1 \leq a,b,c \leq n$$$), and receive the median of $$$\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$$$.
In this case, the median is the $$$2$$$-nd element ($$$1$$$-indexed) of the sequence when sorted in non-decreasing order. The median of $$$\{4,6,2\}$$$ is $$$4$$$ and the median of $$$\{0,123,33\}$$$ is $$$33$$$.
Can you find the secret permutation in not more than $$$2n+420$$$ queries?
Note: the grader is not adaptive: the permutation is fixed before any queries are made.
Input Format:
The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of testcases.
The first line of each testcase consists of a single integer $$$n$$$ $$$(20 \leq n \leq 100000)$$$ — the length of the secret permutation.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100000$$$.
Output Format:
None
Note:
The secret permutation is $$$\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$$$.
For the first query, the values of $$$(a,b,c)$$$ is $$$(1,5,2)$$$. Since $$$p[1]=9$$$, $$$p[5]=16$$$ and $$$p[2]=10$$$. The return value is the median of $$$\{|9-16|,|16-10|,|9-10|\}$$$ which is $$$6$$$.
For the second query, the values of $$$(a,b,c)$$$ is $$$(20,19,2)$$$. Since $$$p[20]=1$$$, $$$p[19]=13$$$ and $$$p[2]=10$$$. The return value is the median of $$$\{|1-13|,|13-10|,|1-10|\}$$$ which is $$$9$$$.
By some miracle, we have figured out that the secret permutation is $$$\{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}$$$. We output it and receive $$$1$$$ from the interactor, meaning that we have guessed the secret permutation correctly.