Park

Vasi finally decided to visit Ruse and take a walk in its park. From her tour guide, she knows that the park has a rectangular shape and its long sides are $N$ units long. On each of those two sides, there are $N + 1$ interesting places (cafes, tennis courts, fountains and so on), so $2N + 2$ interesting places in total. They are numbered and connected with alleys, like it is shown in the figure below ($N = 3$ in this case). The park has a single entrance (the place with number $1$) and a single exit (the place with number $2N + 2$).

All alleys in the park are one-way and when taking a walk one must respect each alley’s direction. The alleys are oriented in such a way that there aren’t any cycles. Also, the entrance is the only place where all alleys are out-going, and the exit is the only place where all alleys are in-going. For all other places the following rule holds: there are both in-going and out-going alleys.

We will say that a particular alley has a positive direction, if it goes from a place with a lower number to a place with a higher one, otherwise we will say it has a negative direction. Vasi is aware that the two alleys from the entrance and the two alleys to the exit have a positive direction (since the entrance has number $1$ and the exit – number $2N + 2$), but she doesn’t know anything about the directions of the other alleys and she needs them to plan her walk in the park.

For the enthusiasts of mathematical and informatical problems at the park’s entrance there is a computer with a special program on it. It answers questions of the following weird type: an arbitrary list of alleys, represented as the numbers of the places they connect, is given to the program and it returns the result of the XOR operation on their directions (where the positive direction will be represented with a 1 and the negative direction with a 0). Let us remind you, that the XOR of two single-bit numbers is 1, if they are different, and 0, if they are the same. In case there are more than two operands, we first perform XOR on the first two, then to the result of that and the third operand and so on. The program is made in such a way that, if the given list only contains a single alley, it will just return its direction.

Vasi wants to find out the directions of all alleys without asking too many questions to the program.

The jury has copied the program from the park’s entrance and now it is uploaded to the grading system. Help Vasi by writing a function run, which is going to be compiled with the jury’s program and will communicate with it by asking questions of the type described above and stating the directions it has found. After it is done running, your function will need to have correctly identified and stated the directions of all alleys in the park.

• $1 ≤ N ≤ 100 000$