Description:
This is an interactive problem.
Khanh has $$$n$$$ points on the Cartesian plane, denoted by $$$a_1, a_2, \ldots, a_n$$$. All points' coordinates are integers between $$$-10^9$$$ and $$$10^9$$$, inclusive. No three points are collinear. He says that these points are vertices of a convex polygon; in other words, there exists a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$ such that the polygon $$$a_{p_1} a_{p_2} \ldots a_{p_n}$$$ is convex and vertices are listed in counter-clockwise order.
Khanh gives you the number $$$n$$$, but hides the coordinates of his points. Your task is to guess the above permutation by asking multiple queries. In each query, you give Khanh $$$4$$$ integers $$$t$$$, $$$i$$$, $$$j$$$, $$$k$$$; where either $$$t = 1$$$ or $$$t = 2$$$; and $$$i$$$, $$$j$$$, $$$k$$$ are three distinct indices from $$$1$$$ to $$$n$$$, inclusive. In response, Khanh tells you:
- if $$$t = 1$$$, the area of the triangle $$$a_ia_ja_k$$$ multiplied by $$$2$$$.
- if $$$t = 2$$$, the sign of the cross product of two vectors $$$\overrightarrow{a_ia_j}$$$ and $$$\overrightarrow{a_ia_k}$$$.
Recall that the cross product of vector $$$\overrightarrow{a} = (x_a, y_a)$$$ and vector $$$\overrightarrow{b} = (x_b, y_b)$$$ is the integer $$$x_a \cdot y_b - x_b \cdot y_a$$$. The sign of a number is $$$1$$$ it it is positive, and $$$-1$$$ otherwise. It can be proven that the cross product obtained in the above queries can not be $$$0$$$.
You can ask at most $$$3 \cdot n$$$ queries.
Please note that Khanh fixes the coordinates of his points and does not change it while answering your queries. You do not need to guess the coordinates. In your permutation $$$a_{p_1}a_{p_2}\ldots a_{p_n}$$$, $$$p_1$$$ should be equal to $$$1$$$ and the indices of vertices should be listed in counter-clockwise order.
Input Format:
None
Output Format:
None
Note:
The image below shows the hidden polygon in the example:
The interaction in the example goes as below:
- Contestant reads $$$n = 6$$$.
- Contestant asks a query with $$$t = 1$$$, $$$i = 1$$$, $$$j = 4$$$, $$$k = 6$$$.
- Jury answers $$$15$$$. The area of the triangle $$$A_1A_4A_6$$$ is $$$7.5$$$. Note that the answer is two times the area of the triangle.
- Contestant asks a query with $$$t = 2$$$, $$$i = 1$$$, $$$j = 5$$$, $$$k = 6$$$.
- Jury answers $$$-1$$$. The cross product of $$$\overrightarrow{A_1A_5} = (2, 2)$$$ and $$$\overrightarrow{A_1A_6} = (4, 1)$$$ is $$$-2$$$. The sign of $$$-2$$$ is $$$-1$$$.
- Contestant asks a query with $$$t = 2$$$, $$$i = 2$$$, $$$j = 1$$$, $$$k = 4$$$.
- Jury answers $$$1$$$. The cross product of $$$\overrightarrow{A_2A_1} = (-5, 2)$$$ and $$$\overrightarrow{A_2A_4} = (-2, -1)$$$ is $$$1$$$. The sign of $$$1$$$ is $$$1$$$.
- Contestant says that the permutation is $$$(1, 3, 4, 2, 6, 5)$$$.