卢浮宫博物馆收藏了历史上最著名的画作之一：由列奥纳多·达·芬奇在 16 世纪创作的《蒙娜丽莎》。

这幅画被放置在一个坚固的玻璃陈列柜中，只有输入 4 个秘密代码才能打开，这些代码需要分别在 4 个不同的键盘上输入。博物馆馆长认为这个系统是牢不可破的，而你的任务就是证明她是错的。

为了帮助你，一位朋友对该系统进行了逆向工程。当一个代码（表示为一个正整数 $C$）在键盘上输入时，键盘会向中央计算机发送该随机数生成器产生的第 $C$ 个值。中央计算机仅考虑从 4 个键盘接收到的 4 个伪随机值的最低 $N$ 位。它计算这些值的按位异或（XOR），如果结果为 0，则打开玻璃陈列柜。伪随机数生成器在题目末尾有详细说明。

另一位朋友找到了每个键盘使用的伪随机种子。有了这些信息，你认为你可以找回解锁《蒙娜丽莎》的 4 个秘密代码。

输入格式

输入包含两行，每行由以空格分隔的整数组成： 第一行包含整数 $N$。 第二行包含四个整数种子。

数据范围

• $1 \leqslant N \leqslant 50$；
• 每个种子在 $0$ 到 $2^{64} - 1$ 之间。

输出格式

输出应包含一行，内容为 4 个整数，即 4 个秘密代码，以空格分隔。每个代码必须小于 $100\,000\,000$。保证至少存在一个解。可能存在多个解，在这种情况下，所有解都将被接受。

伪随机生成器

伪随机生成器在每种编程语言中描述如下。你可以认为该伪随机生成器没有任何偏差。

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;
}

伪随机序列的第 $i$ 个值是对 state 进行第 $i$ 次 xoroshiro128plus 应用的结果。

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;
}

伪随机序列的第 $i$ 个值是对 state 进行第 $i$ 次 xoroshiro128plus 应用的结果。

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

以下循环产生从第一个值开始的伪随机序列：

while True:
result, state = xoroshiro128plus(state)
yield result

样例

输入 1

50
3641603982383516983 445363681616962640 868196408185819179 1980241222855773941

输出 1

287 17609 122886 59914

《蒙娜丽莎》