Find the Array

This is an interactive problem.

There is an array a of length n, consisting of distinct positive integers not greater than 10^9. You must determine every element. You may make at most 30 queries of the following types:

• 1 i (1 <= i <= n) asks for the value of a[i].
• 2 k i1 i2 ... ik (2 <= k <= n) supplies k distinct positions. The judge returns k * (k - 1) / 2 integers: every absolute difference |a[ic] - a[id]| for c < d, in shuffled order.

Once you know the array, print 3 a1 a2 ... an and terminate. This final answer does not count against the 30-query limit.

Interaction Protocol

At the beginning, read one integer n (1 <= n <= 250).

For a type-1 query, print 1 i, then read the value of a[i].

For a type-2 query, print 2 k i1 i2 ... ik, then read the k * (k - 1) / 2 shuffled pairwise absolute differences.

When you know the answer, print 3 a1 a2 ... an and terminate. If either query type returns -1, your query was invalid or exceeded the limit; terminate immediately. End and flush every query line. In C++, std::endl or std::cout.flush() can be used for this.

Example interaction

The following is one possible dialogue. Lines sent by the contestant are shown after the corresponding judge response.

judge:       3
contestant:  1 1
judge:       1
contestant:  1 2
judge:       2
contestant:  2 3 1 2 3
judge:       4 3 1
contestant:  3 1 2 5

Note

In the first query of type 1, we ask the value of a1 and receive 1 as the answer. In the second query of type 2, we ask the value of a2 and receive 2 as the answer. In the query of type 2, we ask all the possible differences between the elements of array with indexes 1, 2 and

3. And we get array 4, 3, 1 as the result. We know that the array contains values |a1 -a2 |, |a1 -a3 |, |a2 -a3 |. Since we already know that |a2 - a1 | = 1, one of the following is true: |a1 - a3 | = 3 and |a2 - a3 | = 4 or |a2 - a3 | = 3 and |a1 - a3 | = 4. The only case that is possible, taking into account the constraints of the problem, is when |a1 - a3 | = 4 and |a2 - a3 | = 3 with a3 = 5. Since we know the values of all the elements of the array, we print them in the last query.