Percy's Attraction Ranking

Charlie is curious about Percy’s true ranking of his attraction towards n individuals. Percy has a unique preference order over these individuals. Charlie is allowed to use up to $2 \times 10^6$ queries of the following two types:

• Truth: Given three positive integers $x$, $y$, $z$ (with $1 \le x,y,z \le n$), Percy must reveal the index of the individual he likes second-most among these three.
• Dare: Given two positive integers $x$, $y$ (with $1 \le x,y \le n$) and provided that at least one of them is Percy’s favorite, Percy must indicate which one he likes more.

The interaction begins by reading a single positive integer $n$. Based on the responses to the queries, Charlie must deduce the complete ranking of the individuals in descending order of Percy’s preference. When ready, he should output his answer using the following command:

3 a1 a2 ... an

Here, a1 is the index of Percy’s most favored individual, and an the least favored.

inputFormat

The first line of input contains a single positive integer $n$ representing the number of individuals. The solution must then perform an interactive session by issuing queries of two types as described above.

outputFormat

When the solution has determined the correct ranking, it should output a single line with the following format:

3 a1 a2 ... an

Here, a1 is the index of the individual that Percy likes the most, and an is the one he likes the least.

sample

3

3 1 2 3