23587번 - Multiplication 다국어인터랙티브

This is an interactive problem.

Jury has chosen a secret odd number $x$ between $1$ and $2^{31}-1$ inclusive. Your task is to guess it. In order to do that, jury gives you an even number $n$. Then you should output exactly $n$ distinct integers between $0$ and $2^{31}-1$ inclusive. After that, jury will multiply each of these numbers by $x$ and take the results modulo $2^{31}$. Then jury will equiprobably choose some random subset of these new numbers of size $n/2$ and give this subset back to you in random order. After that, you should output the correct value of $x$.

In each test, $x$ is chosen in advance and does not change.

Initially, you are given one even integer $n$ ($4 \leq n \leq 10^5$). After that, you should output $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2^{31}-1$) on a single line, separated by spaces. Next, you are given $n/2$ integers $b_1, b_2, \ldots, b_{n/2}$ ($0 \leq b_i \leq 2^{31}-1$) created by the process described above, on a single line, separated by spaces. Finally, you should output a single odd integer $x$: the secret number chosen by the jury ($1 \leq x \leq 2^{31}-1$).

To prevent output buffering, flush the output buffer after each printed line: this can be done by using, for example, fflush (stdout) in C or C++, System.out.flush () in Java, flush (output) in Pascal, or sys.stdout.flush () in Python. Also, do not forget to terminate each line of output with a newline character.