Algosia and Bajtek are very busy. They have no time to invent original problems, and certainly not to send each other $1000 \times 1000$ matrices, which they had to do when participating in this year's final of the Olympiad in Informatics.
Algosia would like to pass a certain positive integer to Bajtek. Unfortunately, as is often the case with them lately, they are separated by a very advanced computer system. Algosia can enter a $10 \times 10$ binary matrix into the computer, then the system permutes the rows and columns of the matrix and sends it to Bajtek. Write a program that helps Algosia and Bajtek encode and decode a number $t$ times.
Interaction
This is an interactive problem. Your program will be run in two copies – one for Algosia and one for Bajtek. Each run will receive the word Algosia or Bajtek in the first line of input, which determines which person's actions this copy of the program is responsible for.
Both programs, immediately after receiving their word, will also receive two integers $n$ and $t$ ($1 \le n \le 3 \cdot 10^{16}$, $1 \le t \le 25$) on the input, representing the upper bound on the encoded numbers and the number of test cases, respectively. Then, the interaction takes place $t$ times.
At the beginning of the $i$-th interaction, Algosia receives one integer $n_i$ ($1 \le n_i \le n$). On the output, she should print 10 lines containing 10 characters each. Each character must be either 0 or 1. The rows and columns of this matrix will be permuted and sent to the input of Bajtek's process in the same format. After receiving the matrix, Bajtek's process should print the number $n_i$ encoded by Algosia to the output. After printing this number, the next test case begins.
After printing each fragment, you must flush the output buffer, for example by calling cout.flush() or fflush(stdout).
Evaluation
The test set consists of 10 groups, for each of which you can get 0 or 1 point. The constraints on the value of $n$ in individual groups are as follows:
| Group Number | $n \le$ |
|---|---|
| 1 | $10^{10}$ |
| 2 | $10^{11}$ |
| 3 | $10^{12}$ |
| 4 | $10^{13}$ |
| 5 | $10^{14}$ |
| 6 | $10^{15}$ |
| 7 | $5 \cdot 10^{15}$ |
| 8 | $10^{16}$ |
| 9 | $2 \cdot 10^{16}$ |
| 10 | $3 \cdot 10^{16}$ |
Local testing
In the Files section, the interactor kodsoc.cpp is available. The interactor provided in the files does not permute the matrix before sending it to Bajtek; apart from this difference, it performs the interaction with the contestants' programs exactly the same as the one checking submissions on the system. It should be run with the command:
python3 kodrun.py [solution] < [test]
where the files kodsoc.cpp and oi.h must be in the same folder. The format in which the interactor accepts input is described in the comment in the kodsoc.cpp file. Additional options for the kodrun.py script can be found by running the command python3 kodrun.py -h.
Examples
Input 1
Algosia 20 2 12
Output 1
1110000000 1000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
Input 2
Bajtek 20 2 0000000000 0000100000 0000000000 0000000000 0000000000 0000000000 0100100001 0000000000 0000000000 0000000000
Output 2
12
Fair play rules
Communicating between programs in any way other than through the game flow, e.g., by sending a move by one program with a delay and reading the clock by the other, is prohibited. In case the Jury finds an attempt to communicate between programs in an unauthorized manner, the submission may be removed, and in egregious cases, a decision may be made to disqualify the author of this submission from the entire competition.