CF1254C.Point Ordering

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

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

这是一个交互式问题。

Khanh 在笛卡尔平面上有 $n$ 个点，记为 $a_1, a_2, \ldots, a_n$。所有点的坐标均为介于 $-10^9$ 与 $10^9$（含端点）之间的整数。任意三点不共线。他声称这些点构成一个凸多边形的顶点；换言之，存在 $1$ 到 $n$ 的一个排列 $p_1, p_2, \ldots, p_n$，使得多边形 $a_{p_1} a_{p_2} \ldots a_{p_n}$ 是凸的，且顶点按逆时针顺序列出。

Khanh 向你给出数字 $n$，但隐藏了各点的坐标。你的任务是通过多次查询来猜出上述排列。每次查询中，你向 Khanh 提供四个整数 $t$, $i$, $j$, $k$：其中 $t = 1$ 或 $t = 2$；$i$, $j$, $k$ 是 $1$ 到 $n$ 中互不相同的下标。Khanh 将返回以下信息：

• 若 $t = 1$，则返回三角形 $a_i a_j a_k$ 面积的两倍；
• 若 $t = 2$，则返回向量 $\overrightarrow{a_i a_j}$ 与 $\overrightarrow{a_i a_k}$ 的叉积的符号。

回忆一下：向量 $\overrightarrow{a} = (x_a, y_a)$ 与向量 $\overrightarrow{b} = (x_b, y_b)$ 的叉积为整数 $x_a \cdot y_b - x_b \cdot y_a$。一个数的符号定义为：若其为正，则为 $1$；否则为 $-1$。可以证明：上述查询中得到的叉积不可能为 $0$。

你最多可进行 $3 \cdot n$ 次查询。

请注意，Khanh 在回答你的查询过程中固定各点坐标，不会更改。你无需猜测各点的具体坐标。在你输出的排列 $a_{p_1}a_{p_2}\ldots a_{p_n}$ 中，必须满足 $p_1 = 1$，且顶点下标需按逆时针顺序列出。

交互方式

首先读入 $n$（$3 \leq n \leq 1\,000$）——即顶点数量。

为进行一次查询，请在单独一行中输出四个整数 $t$, $i$, $j$, $k$（$1 \leq t \leq 2$, $1 \leq i, j, k \leq n$）。其中 $i$, $j$, $k$ 必须互不相同。

然后读入一个整数，即该查询的答案（如上所述）。可以证明：每次查询的答案恒为整数。

当你确定了排列，请先输出一个数字 $0$，再在同一行中输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$。

每次输出查询后，请务必输出换行符并刷新输出缓冲区；否则将收到“空闲超限”（Idleness limit exceeded）错误。为此，请使用以下方式：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参考相应文档。

Hack 格式

用于 hack 的输入格式如下：

第一行为一个整数 $n$（$3 \leq n \leq 1\,000$）——即顶点数量。

接下来 $n$ 行中的第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$）——表示点 $a_i$ 的坐标。

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

下图展示了示例中的隐藏多边形：

示例中的交互过程如下：

• 选手读入 $n = 6$。
• 选手提出一个查询，其中 $t = 1$，$i = 1$，$j = 4$，$k = 6$。
• 评委会回答 $15$。三角形 $A_1A_4A_6$ 的面积为 $7.5$。注意：返回值是该三角形面积的两倍。
• 选手提出一个查询，其中 $t = 2$，$i = 1$，$j = 5$，$k = 6$。
• 评委会回答 $-1$。向量 $\overrightarrow{A_1A_5} = (2, 2)$ 与 $\overrightarrow{A_1A_6} = (4, 1)$ 的叉积为 $-2$，其符号为 $-1$。
• 选手提出一个查询，其中 $t = 2$，$i = 2$，$j = 1$，$k = 4$。
• 评委会回答 $1$。向量 $\overrightarrow{A_2A_1} = (-5, 2)$ 与 $\overrightarrow{A_2A_4} = (-2, -1)$ 的叉积为 $1$，其符号为 $1$。
• 选手给出排列 $(1, 3, 4, 2, 6, 5)$。