Point Ordering
Contest: Codeforces Round 601 (Div. 1)
Difficulty rating: 2300
Tags: constructive algorithms, geometry, interactive, math

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.

Interaction format:
You start the interaction by reading $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) — the number of vertices.

To ask a query, write $$$4$$$ integers $$$t$$$, $$$i$$$, $$$j$$$, $$$k$$$ ($$$1 \leq t \leq 2$$$, $$$1 \leq i, j, k \leq n$$$) in a separate line. $$$i$$$, $$$j$$$ and $$$k$$$ should be distinct.

Then read a single integer to get the answer to this query, as explained above. It can be proven that the answer of a query is always an integer.

When you find the permutation, write a number $$$0$$$. Then write $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ in the same line.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hack format

To hack, use the following format:

The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) — the number of vertices.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinate of the point $$$a_i$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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)$$$.

Example input:
6

15

-1

1

Example output:
1 1 4 6

2 1 5 6

2 2 1 4

0 1 3 4 2 6 5

Editorial:
Let's start by choosing vertices $$$1$$$ and $$$2$$$ as pivots.
Recall that if the cross product of two vectors $$$\vec{A}$$$ and $$$\vec{B}$$$ is positive, point $$$B$$$ lies to the left of $$$\vec{A}$$$; if the product is negative, point $$$B$$$ lies to the right of $$$\vec{A}$$$; and if the product is zero, the 3 points $$$(0,0)$$$, $$$A$$$, $$$B$$$ are collinear.
With $$$n-2$$$ queries of type 2, we can know which vertices lie to the left or to the right of edge $$$1-2$$$ and then solve the two sides separately.
Consider the left side and there are $$$a$$$ vertices lie to the left, we can use $$$a$$$ queries of type 1 to calculate the distance from those vertices to edge $$$1-2$$$ (the distance from vertex $$$X$$$ to edge $$$1-2$$$ is twice the area of the triangle forms by $$$1$$$, $$$2$$$, $$$X$$$, divides by the length of edge $$$1-2$$$).
Let Y be the farthest from $$$1-2$$$ (there can be at most 2 such vertices). We can use $$$a-1$$$ queries of type 2 to see if the others vertices lie between $$$1, Y$$$ or between $$$Y, 2$$$, then sort them counter-clockwise with the asked distances.
So we will use $$$n-2$$$ queries to calculate the distances from vertices $$$3, 4, .. n$$$ to edge $$$1-2$$$ and at most $$$n - 3$$$ for the latter step. This solution uses at most $$$3n-7$$$ queries.
Another solution is to find the vertex that is consecutive to $$$1$$$ in $$$n-2$$$ queries and do the same as the solution above.