We have $n$ weights, numbered from $1$ to $n$. Among these, one specific weight, numbered $i$, is defective and has a mass of $2$ grams, while all other weights have a mass of $1$ gram each. We also have a balance scale available. For each measurement, you can select a unique set of weights to place on either side of the scale. After each measurement, we will inform you whether the left side is heavier, the right side is heavier, or if both sides are balanced. Your task is to identify this defective weight.

If finding weight $i$ requires $f_i$ weighings, ensure that $\max_{i \in [1,n]} f_i$ is as small as possible.

Constraints $1\le n\le 10^5$.

Interaction Protocol

The first line of input is a single integer $n$, indicating the number of weights. The following input of your program depends on your output.

If you output 1 a b, this means that you are going to put a weights on the left, and b weights on the right. Then you should output a integers, which are the indexes of the weights you want to put on the left. And then b integers similarly. The judger will give you a result of -1 if the a weights are lighter, 0 if the same, and 1 otherwise.

If you output 2 x, this means that you have determined that the x-th weight is of $2$ grams.

Example

This is an example of the interaction history.

Suppose that we have 5 weights, and the 4th is defective.

• Your program receives input 5
• Your program outputs

1 1 2
1
2 3

• Because $1<1+1$, your program receives the result -1
• Your program outputs

1 1 1
4
5

• Because $2>1$, your program receives the result 1
• Your program have found the answer, and outputs

4

Attention

You need to ensure that your output is flushed so that the judger can receive your request. This is normally done if printf ending with \n, or std::cout with std::endl;

If you need to do it manually for C, here's how:

fflush(stdout);

Or in C++:

std::cout << std::flush;