eolymp
bolt
Try our new interface for solving problems
Problems

Central Element

Central Element

Time limit 1 second
Memory limit 64 MiB

This is an interactive problem.

There is a permutation P of numbers 1 through n, not known to you, P = <P_1, P_2, …, P_n>. You can ask the following type of questions: Given three distinct positions i, j and k, which of P_i, P_j and P_k is central? Element is central if it is neither minimal nor maximal.

For example, if the permutation is <2,1,4,3>, and you ask about positions 1, 2, and 3, you receive 2, because 2 is the central element of the set {P1, P2, P3}= {2,1,4}. Note that you don't get the information at which position among 1, 2, and 3 it is located.

Your task is to find the permutation P. Actually, for each permutation P there is a set S(P) of permutations that cannot be distinguished from P using the allowed questions. You must find any permutation from this set.

Input data

The first line of the standard input contains n, the size of the permutation (3 <= n <=200).

Each of the next lines of the standard input contains response to your question – the number that is central among the numbers at the asked positions.

Interaction

First, your program must read from the standard input one line with the integer n, the size of the permutation.

The program must write to the standard output one line with three positions that you ask a question about and wait for a line in the standard input with a response, then write next question and read next response, and so on until you know the permutation P up to S(P).

Once you know the answer, output one line with the word ”OK” and the permutation P.

Output data

When you're asking questions, each line of the standard output should contain three different integers from the range of 1 to n, space-separated. You can ask at most 2 000 questions.

When you're stating the answer, the line of the standard output should contain the word ”OK”, and the numbers P_1, P_2, …, P_n, all space-separated. After printing this line your program must exit.

You must flush standard output after printing each line.

Examples

Input example #1
4
2 1 4 3
Output example #1
0
8 questions
Author Mikhail Dvorkin