This is an interactive problem.
The pink soldiers hid from you $$$n$$$ ($$$3 \le n \le 1500$$$) fixed points $$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$$, whose coordinates are not given to you. Also, it is known that no two points have the same coordinates, and no three points are collinear.
You can ask the Frontman about three distinct indices $$$i$$$, $$$j$$$, $$$k$$$. Then, he will draw a triangle with points $$$(x_i,y_i)$$$, $$$(x_j,y_j)$$$, $$$(x_k,y_k)$$$, and respond with the following:
Using at most $$$\mathbf{75}$$$ queries, you must find any triangle formed by three of the points, not containing any other hidden point inside.
Do note that the Frontman may be adaptive while choosing the point to give you. In other words, the choice of the point can be determined by various factors including but not limited to the orientation of points and the previous queries. However, note that the sequence of points will never be altered.
Hacks are disabled for this problem. Your solution will be judged on exactly $$$\mathbf{35}$$$ input files, including the example input.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). The description of the test cases follows.
The first line of each test case contains one positive integer $$$n$$$ — the number of points ($$$3 \le n \le 1500$$$).
Afterwards, you can output the following on a separate line to ask a query:
Then, the interactor responds with one integer on a new line:
If you want to print an answer, you can output the following on a separate line:
Then, the following interaction happens:
Do note that printing the answer does not count towards the number of queries made.
Do note that the interactor may be adaptive while choosing the point to give you. In other words, the choice of the point can be determined by various factors including but not limited to the orientation of points and the previous queries. However, note that the sequence of points will never be altered.
After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.
If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.
Hacks
Hacks are disabled for this problem. Your solution will be judged on exactly $$$\mathbf{35}$$$ input files, including the example input.
$$$^{\text{∗}}$$$To flush, use:
2 6 5 4 0 3
? 1 2 3 ? 1 5 3 ? 2 5 6 ! 2 5 6 ! 1 2 3
In the first test case, the points are $$$(3,0),(0,3),(5,2),(3,1),(2,2),(4,4)$$$.
The triangles corresponding to the three queries are as follows.
You can see that the triangle formed by $$$(0,3)$$$, $$$(2,2)$$$, $$$(4,4)$$$ does not contain any other hidden point inside. Therefore, it is a valid answer.
Do note that the interaction example only shows a valid interaction, and not necessarily the actual response. For example, it is possible that the Frontman responds with $$$4$$$ when you query "? 1 2 3". However, as the Frontman does not alter the sequence of points, he never responds with $$$6$$$ for the same query.
In the second test case, there are only $$$3$$$ points. Therefore, we know that the unique triangle formed by the points does not contain any other hidden point inside.