Background

Note: Please do not submit code maliciously and waste judging resources.

A group of people are at a party, playing “Truth or Dare”.

Problem Description

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.

Input Format

(See the Description section.)

Output Format

(See the Description section.)

5

3

5

1 1 2 3

2 1 5

3 5 2 4 3 1

Hint

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