The painting is enclosed in a rock-solid glass chamber that can only be opened with 4 secret codes that need to be entered on 4 different keypads. The head of the museum thinks that this system is unbreakable, and your task is to prove her wrong.
To help you, a friend reverse-engineered the system. When a code (represented by a positive integer $C$) is entered on a keypad, the keypad sends the $C$-th value produced by a random number generator to a central computer. The central computer only considers the N least significant bits of the 4 pseudo-random values it receives from the 4 keypads. It computes their bitwise XOR (exclusive or) and opens the glass chamber if the result is 0. The pseudo-random number generator is described at the end of the problem statement.
Another friend found the pseudo-random seeds used by each keypad. With all this information, you think that you can retrieve the 4 secret codes unlocking Mona Lisa.
The input comprises two lines, each consisting of integers separated with single spaces:
*Limits*
The output should consist of a single line, whose content is 4 integers, the 4 secret codes, separated with single spaces. Each code must be less than $100000000$. It is guaranteed that at least one solution will exist. Multiple solutions may exist, in which case they will all be accepted.
Pseudo-Random Generator The pseudo-random generator is described next in each programming language. You can expect that this pseudo-random generator is not biased in any way.
*C/C++*
*Java*
The i-th value of the pseudo-random sequence is the result of the i-th application of xoroshiro128plus on 'state'.
*Python 2 / Python 3*
## Input
The input comprises two lines, each consisting of integers separated with single spaces: The first line contains the integer $N$. The second line contains the four integer seeds. *Limits* $1 <= N <= 50$; each seed is between $0$ and $2^(64) -1$.
## Output
The output should consist of a single line, whose content is 4 integers, the 4 secret codes, separated with single spaces. Each code must be less than $100000000$. It is guaranteed that at least one solution will exist. Multiple solutions may exist, in which case they will all be accepted.
[samples]
## Note
Pseudo-Random Generator The pseudo-random generator is described next in each programming language. You can expect that this pseudo-random generator is not biased in any way.*C/C++* typedef unsigned long long uint64;uint64 state[2] = { seed, seed ^ 0x7263d9bd8409f526 };uint64 xoroshiro128plus(uint64 s[2]) { uint64 s0 = s[0]; uint64 s1 = s[1]; uint64 result = s0 + s1; s1 ^= s0; s[0] = ((s0 « 55) | (s0 » 9)) ^ s1 ^ (s1 « 14); s[1] = (s1 « 36) | (s1 » 28); return result;} The i-th value of the pseudo-random sequence is the result of the i-th application of xoroshiro128plus on 'state'.*Java* long[] state = { seed, seed ^ 0x7263d9bd8409f526L };long xoroshiro128plus(long[] s) { long s0 = s[0]; long s1 = s[1]; long result = s0 + s1; s1 ^= s0; s[0] = ((s0 « 55) | (s0 »> 9)) ^ s1 ^ (s1 « 14); s[1] = (s1 « 36) | (s1 »> 28); return result;}The i-th value of the pseudo-random sequence is the result of the i-th application of xoroshiro128plus on 'state'.*Python 2 / Python 3* state = [seed, seed ^ 0x7263d9bd8409f526]def xoroshiro128plus(s): s0, s1 = s result = (s0 + s1) % 2**64 s1 ^= s0; new_state = [(((s0 « 55) | (s0 » 9)) ^ s1 ^ (s1 « 14)) % 2**64, ((s1 « 36) | (s1 » 28)) % 2**64] return result, new_state The following loop yields the pseudo-random sequence starting from its first value: while True: result, state = xoroshiro128plus(state) yield result
Let $ s_1, s_2, s_3, s_4 \in \mathbb{N} $ be the known initial seeds for the four keypads.
Let $ f: \mathbb{N} \to \mathbb{N} $ be the deterministic function implementing xoroshiro128plus.
Let $ v_i(c) = f^c(s_i) $ denote the $ c $-th value generated by keypad $ i $ starting from seed $ s_i $.
Let $ N \in \mathbb{Z}^+ $ be the number of least significant bits considered.
Let $ \text{mask} = 2^N - 1 $.
Define $ b_i(c) = v_i(c) \& \text{mask} $ as the $ N $-bit truncated value from keypad $ i $ when code $ c $ is entered.
**Objective**: Find integers $ c_1, c_2, c_3, c_4 \in \mathbb{Z}^+ $, each $ < 10^8 $, such that:
$$
(b_1(c_1) \oplus b_2(c_2) \oplus b_3(c_3) \oplus b_4(c_4)) = 0
$$