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).
Notes
- The interaction described below corresponds to the first sample test named
kod0a.in. - Both programs start at the same time. The execution time is measured as the wall-clock time from the start to the end of the interactor.
- Algosia receives the next number only after the previous one has been decoded by Bajtek.
- After reading $n$ and $t$, Bajtek's process can use the time during which Algosia's process is encoding the first number to perform any calculations instead of blocking on input. In extreme cases, this can speed up the program execution by a factor of two.
Examples
Input 1
Algosia 20 2 12 11
Output 1
1110000000 1000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 1110000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Input 2
Bajtek 20 2 0000000000 0000100000 0000000000 0000000000 0000000000 0000000000 0100100001 0000000000 0000000000 0000000000 0000000100 0000000100 1000000101 0000000100 0000000100 0000000100 0000000100 0000000100 0000000100 0000000100
Output 2
12 11
Evaluation
| 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.
Trial runs
Trial runs are available for this task. In a trial run, you must provide the input for the interactor. The trial run returns the program verdict. The interactor used in trial runs is the same as the one used for official submissions.
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.