A. Magician
time limit per test
5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

A magician is going to play a game with $$$N = 20$$$ gnomes. Each gnome $$$i$$$ wears a hat of color $$$C_i$$$ ($$$1 \leq C_i \leq 5 \cdot 10^5$$$). Each gnome can see the color of all other gnomes' hats except his own. The game consists of two phases:

  • Phase 1: Each gnome has a card. They are allowed to write either $$$0$$$ or $$$1$$$ on the card. They cannot communicate with each other while writing their numbers, i.e., all of them write simultaneously and independently.
  • Phase 2: The magician collects all the cards from the gnomes and creates an array $$$A$$$ of size $$$N$$$, where $$$A_i$$$ is the number written by the $$$i$$$-th gnome (the order is preserved). Each gnome must now deduce the color of his own hat. All of them announce their guesses simultaneously.

To prevent cheating, the interaction will be split into two phases:

  • In the first phase, you will specify for each gnome what number they write on their card, presented in a shuffled order.
  • Similarly, the second phase will proceed in random order. See the interaction section for more details.
Interaction

First, you must read a line containing a single integer $$$T$$$ ($$$1 \leq T \leq 4 \cdot 10^4$$$), the number of times a gnome will be asked to write a number across all tests.

For each gnome, you must first read a line containing $$$21$$$ space-separated integers: $$$i$$$ — the index of the gnome being asked to write a number and $$$C_1, C_2, \ldots, C_{20} \ (1 \leq i \leq 20)$$$ — the colors of the other gnomes. Note that $$$C_i = 0$$$ always (as they can't see their own hat).

Then, you should print one line containing one integer, which is the value that the $$$i$$$-th gnome writes on the card.

Now, phase two begins. First, you must read a line containing a single integer $$$K$$$ ($$$1 \leq K \leq 4 \cdot 10^4$$$) denoting the number of times a gnome shares the color of their hat across all tests. Then, a description of the interaction for $$$K$$$ gnomes follows:

For each gnome, you must first read a line containing $$$21$$$ space-separated integers and one string consisting of $$$20$$$ characters: $$$i, C_1, C_2, \ldots, C_{20}, A \ (1 \leq i \leq 20)$$$. Gnome $$$i$$$ is going to tell the color of his hat in some test, identified by the colors of the other gnomes' hats, which are given by the array $$$C$$$ (same as in phase 1). Note that $$$C_i = 0$$$ always. The string $$$A$$$ represents the values written on the cards by each gnome.

Then, you should print one line containing one integer, which is the color of the $$$i$$$-th gnome's hat.

After outputting each line, don't forget to flush the output. For example:

  • fflush(stdout) in C/C++;
  • System.out.flush() in Java;
  • sys.stdout.flush() in Python;
  • flush(output) in Pascal;
  • See the documentation for other languages.
Example
Input
20
1 0 2 3 4 ... 5 1 2 3 4 5

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

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

...
20
1 0 2 ... 4 5 00100000000000000000

2 1 0 ... 4 5 00100000000000000000

7 1 2 ... 4 5 00100000000000000000

...
Output


0

0

1
...


1

2

2
...
Note

Sample has only one test, and it has the following color configuration:

$$$C = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]$$$