There is a sequence $a_0, \dots, a_{n-1}$ consisting of $0$s and $1$s. You do not know the elements of this sequence, but you can ask for the sum of any pair of distinct elements of the sequence. Your task is to guess the sequence using a small number of such queries.

Communication

This is an interactive task. Communication with the grader can be performed either using a library or via standard input and output. You choose which option you prefer. You must not use both methods simultaneously.

Your program must not open any files. The program may use standard diagnostic output (stderr), but keep in mind that this consumes valuable time. Any redundant data written to standard output may be treated as an incorrect answer.

Option 1: Communication via library

In this option, your program must not use standard input and output.

C++

At the beginning of the program, you must include: * #include "zerlib.h"

The library provides the following functions: int daj_n() – The function returns an integer $n$, representing the length of the unknown sequence of $0$s and $1$s. This function can be called any number of times. int suma(int i, int j) – The function returns $a_i + a_j$, if $0 \le i, j < n$ and $i \neq j$. Otherwise, calling it will result in an incorrect answer. * void odpowiedz(std::vector<int> a) – This function allows you to submit the resulting sequence. It must be called exactly once. It takes an array $a[0..n-1]$ given as a std::vector<int> representing the resulting sequence $a[0], \dots, a[n-1]$. If the sequence provided in the function is incorrect or its length is different from $n$, it will result in an incorrect answer. After calling this function, the program must terminate.

Python

At the beginning of the program, you must include: * from zerlib import daj_n, suma, odpowiedz

The library provides the following functions: daj_n() -> int – The function returns an integer $n$, representing the length of the unknown sequence of $0$s and $1$s. This function can be called any number of times. suma(i : int, j : int) -> int – The function returns $a_i + a_j$, if $0 \le i, j < n$ and $i \neq j$. Otherwise, calling it will result in an incorrect answer. * odpowiedz(a : list[int]) – This function allows you to submit the resulting sequence. It must be called exactly once. It takes an array $a[0..n-1]$ given as a list, representing the resulting sequence $a[0], \dots, a[n-1]$. If the sequence provided in the function is incorrect or its length is different from $n$, it will result in an incorrect answer. After calling this function, the program must terminate.

Option 2: Communication via standard input/output

The first line of standard input will contain a single integer $n$, representing the length of the unknown sequence of $0$s and $1$s.

To ask a query to the library, you must print two integers $i$ and $j$ such that $0 \le i, j < n$ and $i \neq j$. If the numbers do not satisfy these conditions, it will result in an incorrect answer. The numbers must be printed to standard output, separated by a single space and followed by a newline character. Then, you must read one integer from standard input, representing $a_i + a_j$.

At the end, you must submit the resulting sequence. To do this, you must print the number $n$ in one line, and in the second line, a sequence of $n$ numbers separated by single spaces, representing the resulting sequence $a[0], \dots, a[n-1]$. If the printed sequence is incorrect or its length is different from $n$, it will result in an incorrect answer. After printing the sequence, the program must terminate.

C++, stream I/O

You must include the appropriate header (#include <iostream>). At the end of each line when printing, you must use std::endl.

C++, stdio

You must include the appropriate header (#include <cstdio>). After printing each line, you must call fflush(stdout).

Python

After printing each line, you must set flush = True.

Subtasks

The test set is divided into the following subtasks.

The library does not have to generate the sequence $a_0, \dots, a_{n-1}$ at the beginning of the interaction with your program. It may change the elements of the sequence during the interaction, as long as the new elements are still consistent with the results returned by previous calls to the suma function.

If $m$ is the maximum number of calls to the suma function that your program performed in a single test case, your solution will receive the following percentage of points for the test:

Examples

Input 1

5

Output 1

0 1
1
1 2
1
3 4
2
0 3
2
5
1 0 1 1 1