C. Find the Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is an array $$$a$$$ of length $$$n$$$, consisting of distinct integers. It is guaranteed that every element of the array is a positive integer less than or equal to $$$10^9$$$. You have to find out the values of all the elements of it.

To do so, you can make up to $$$30$$$ queries of the following two types:

  • "1 $$$i$$$" $$$(1 \le i \le n)$$$ — ask the value of $$$a_{i}$$$
  • "2 $$$k \ i_1, i_2, \ldots, i_k$$$" ($$$2 \le k \le n$$$, $$$1 \le i_j \le n$$$, all $$$i_j$$$ must be distinct) — the number $$$k$$$ and $$$k$$$ positions in the array. As the answer to this query you will receive $$$\frac{k \cdot (k-1)}{2}$$$ integers — $$$\mid a_{i_c} - a_{i_d} \mid$$$ for every $$$c < d$$$. In other words, you will receive $$$\frac{k \cdot (k-1)}{2}$$$ absolute values of differences between all pairs of elements that are on positions $$$i_1, i_2, \dots, i_k$$$. Note that the answer on query $$$2$$$ is randomly shuffled.

Once you know the answer, print it using the following query:

  • "3 $$$a_1, a_2, \ldots, a_n$$$" ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$. After this query, your program must terminate. This query doesn't count (i.e. you can make up to $$$30$$$ queries of either of the first two types plus $$$1$$$ query of the third type).
Interaction

At the beginning, your program should read one integer $$$n$$$ ($$$1 \leq n \leq 250$$$) — the number of elements.

In order to make a query of the first type, print "1 $$$i$$$" ($$$1 \le i \le n$$$). After this query, read one integer — the value of $$$a_i$$$.

In order to make a query of the second type, print "2 $$$k$$$" ($$$2 \le k \le n$$$). Then in the same line print $$$k$$$ space-separated distinct integers — $$$i_1, i_2, \dots, i_k$$$, ($$$1 \le i_j \le n$$$). After this query read $$$\frac{k \cdot (k-1)}{2}$$$ integers — $$$\mid a_{i_c} - a_{i_d} \mid$$$ for every $$$c < d$$$. These values will be given in random order.

Once you know the answer, print "3". Then in the same line, print $$$n$$$ space-separated integers — $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$). Your program must terminate after this query.

If for either of two first queries you get one number $$$-1$$$ as the answer, then it means that you made more queries than allowed, or made an invalid query. Your program should immediately terminate (for example, by calling exit(0)). You will receive "Wrong Answer". If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Wall time-limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python.

Precisely follow this format of interaction.

Example
Input
3

1

2

4 3 1
Output

1 1

1 2

2 3 1 2 3

3 1 2 5
Note

In the first query of type $$$1$$$, we ask the value of $$$a_1$$$ and receive $$$1$$$ as the answer.

In the second query of type $$$2$$$, we ask the value of $$$a_2$$$ 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 $$$|a_1 - a_2|, |a_1 - a_3|, |a_2 - a_3|$$$. Since we already know that $$$|a_2 - a_1| = 1$$$, one of the following is true: $$$|a_1 - a_3| = 3$$$ and $$$|a_2 - a_3| = 4$$$ or $$$|a_2 - a_3| = 3$$$ and $$$|a_1 - a_3| = 4$$$. The only case that is possible, taking into account the constraints of the problem, is when $$$|a_1 - a_3| = 4$$$ and $$$|a_2 - a_3| = 3$$$ with $$$a_3 = 5$$$.

Since we know the values of all the elements of the array, we print them in the last query.