#215365. [SWERC 2018] Mona Lisa

The Louvre museum hosts one of the most famous paintings ever made: Mona Lisa, painted by Leonardo da Vinci in the 16th century.

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 ) is entered on a keypad, the keypad sends the -th value produced by a random number generator to a central computer. The central computer only considers the 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:

• The first line contains the integer .
• The second line contains the four integer seeds.

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 xoshiro128plus(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 -th value of the pseudo-random sequence is the result of the -th application of xoshiro128plus on state.

Java

long[] state = { seed, seed ^  0x7263d9bd8409f526L };
long xoshiro128plus(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 -th value of the pseudo-random sequence is the result of the -th application of xoshiro128plus on state.

Python 2 / Python 3

state = [seed, seed ^ 0x7263d9bd8409f526]
def xoshiro128plus(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 = xoshiro128plus(state)
    yield result

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 100 000 000. It is guaranteed that at least one solution will exist. Multiple solutions may exist, in which case they will all be accepted.

样例输入 1

50
3641603982383516983 445363681616962640 868196408185819179 1980241222855773941

样例输出 1

287 17609 122886 59914

Limits

• ;
• each seed is between 0 and .