Description

We randomly choose three numbers $R_0, R_1, R_2$, and generate the whole sequence $R$ by the following rule:

$$R_n = R_{n-2} \oplus R_{n-1}$$

Here, $\oplus$ denotes the XOR operation.

In addition, we have a function $M$, which is a bijection. That is, we guarantee that for $x \not= y$, $M(x) \not= M(y)$.

Your goal is to determine $R_0, R_1, R_2, M(0), M(1), \ldots, M(255)$ after making multiple queries.

Interaction

Your program should read from standard input and write to standard output.

You may output an integer $A$ to standard output. If this is your $N$-th query, you will read:

$$M(A \oplus R_{N-1})$$

If you have obtained all answers, output a line with the string SOLUTION, and then output $259$ lines, which are $R_0, R_1, R_2, M(0), M(1), \ldots, M(255)$.

Remember to flush the output buffer after printing each line.

Output Format

Hint

Sample

(Because the sample testdata is hard to present, it is placed here.)

We manually set $R_0 = 0, R_1 = 1, R_2 = 3, M(i) = (i + 1) \bmod 256$.

Then $R_3 = 1$.

Output	Input	Explanation
$10$	$11$	$M(10 \oplus 0) = M(10) = 11$
	$12$	$M(10 \oplus 1) = M(11) = 12$
$11$	$9$	$M(11 \oplus 3) = M(8) = 9$
$12$	$14$	$M(12 \oplus 1) = M(13) = 14$
…		Some outputs are omitted.
SOLUTION

Constraints and limits

For $100\%$ of the testdata, it is guaranteed that the input numbers, output numbers, the array $R$, and both $x$ and $M(x)$ in $M(x)$ are all $\ge 0$ and $\le 255$.

Scoring policy

If the number you output is not within the range above, you will fail.

Your number of queries must be less than $320$, otherwise, you will fail.

Hint

Sample

(Because the sample testdata is hard to present, it is placed here.)

We manually set $R_0 = 0, R_1 = 1, R_2 = 3, M(i) = (i + 1) \bmod 256$.

Then $R_3 = 1$.

Output	Input	Explanation
$10$	$11$	$M(10 \oplus 0) = M(10) = 11$
	$12$	$M(10 \oplus 1) = M(11) = 12$
$11$	$9$	$M(11 \oplus 3) = M(8) = 9$
$12$	$14$	$M(12 \oplus 1) = M(13) = 14$
…		Some outputs are omitted.
SOLUTION

Constraints and limits

For $100\%$ of the testdata, it is guaranteed that the input numbers, output numbers, the array $R$, and both $x$ and $M(x)$ in $M(x)$ are all $\ge 0$ and $\le 255$.

Scoring policy

If the number you output is not within the range above, you will fail.

Your number of queries must be less than $320$, otherwise, you will fail.

Hint

How to flush the output buffer:

C:

printf("%d\n", q);
fflush(stdout); 

C++:

cout<<q<< '\n';
cout.flush();

Pascal：

writeln(q);
flush(output);

Note

This problem is translated from Balkan Olympiad in Informatics 2011 Day 1 T2 decrypt.

Thanks to

ing the interactive library.

Translated by ChatGPT 5