This is an interactive problem.

Jury has hidden a binary sequence of length n. You know only the length n.

You should divide this binary sequence into two subsets with equal number of ones.

You can make queries of the following three types:

1 i (1 ≤ i ≤ n) - xor the i-th bit (you can make up to 777 queries for this type)

2 - ask number of ones in the sequence (you can ask only once)

3 - print the answer (Look at the output section)

Input

The first line contains single integer n (1 ≤ n ≤ 777) - the length of the hidden binary sequence. You should read this integer first.

Output

When your program is ready to print the answer, print two lines.

In the first line print 3.

In the second line print n integers a1, a2, ..., an (1 ≤ ai ≤ 2) - ai = 1 if i-th bit in the first subset, ai = 2 if in the second subset.

Your program should terminate after printing the answer.