P8052 [ZYOI Round1] Truth / Truth or Dare

**Note: Please do not submit code maliciously and waste judging resources.** A group of people are at a party, playing “Truth or Dare”.

Charlie is now targeting someone named Percy. They plan to determine Percy’s ranking of favorability toward $n$ people of the opposite sex. Specifically, Charlie can make two types of requests: 1. **[Truth]** Given $3$ positive integers $x, y, z$, Percy must answer the ID of the person he likes the *second most* among these three. Constraints: $1 \le x, y, z \le n$. 2. **[Dare]** Given $2$ positive integers $x, y$, Percy must hug the one he likes more between them. Constraints: $1 \le x, y \le n$, and it is guaranteed that among $x, y$, **at least one** is Percy’s favorite overall. Charlie wants to achieve his goal using at most $2 \times 10^6$ queries. **Interactive format:** At the beginning, read one positive integer $n$ to start the interaction. You may output three types of messages: 1. `1 x y z`, which represents a “Truth” query, then read the result. 2. `2 x y`, which represents a “Dare” query, then read the result. 3. `3 a1 a2 ... an`, which means you have obtained the answer. Output, in order, the IDs of Percy’s favorite, second favorite, ..., up to the $n$-th favorite.

(See the Description section.)

(See the Description section.)

**The above input and output are only to demonstrate the interactive format, and may not be logically consistent.** For $20\%$ of the testdata, $1 \le n \le 10$. For $40\%$ of the testdata, $1 \le n \le 100$. For $60\%$ of the testdata, $1 \le n \le 10^3$. For $80\%$ of the testdata, $1 \le n \le 10^4$. For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$. Note that invalid output may cause mysterious issues such as WA / RE / TLE / MLE. Translated by ChatGPT 5