C0018 [CTSC2014Day1-C]随机数

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是，有计算机生成的随机数序列并非真正的随机数，而是由一定法则生成的伪随机数。

某一天，露露了解了一种生成随机数的方法，成为 Mersenne twister。给定初始参数 $m∈Z^+，x∈Z^+∩[0,2m)$ 和初值 $M_0∈Z^+∩[0,2m)$，它通过下列递推式构造伪随机数列 $\{M_n\}$：

$M_n=\begin{cases} 2M_{n-1}, & 2M_{n-1}<2^m \\ (2M_{n-1}-2^m) \text{XOR} x, &2M_{n-1} \ge 2^m\end{cases}$

其中 XOR 是二进制异或运算（C/C++中的 ^ 运算）。而参数 $x$ 的选取若使得该数列在长度趋于无穷时，近似等概率地在 $Z^+∩(0,2m)$ 中取值，就称 $x$ 为好的。例如，在 $m>1$ 时 $x=0$ 就显然不是好的。

在露露向伙伴们介绍了 Mersenne twister 之后，花花想用这一些经典的随机性测试来检验它的随机性强度。为此，花花使用计算机计算了一些 $M_k$。

但细心的萱萱注意到，花花在某次使用二进制输入 $k$ 时，在末尾多输入了 $l$ 个 0。她正想告诉花花这个疏忽，然而花花已经计算并记录了错误的 $M_k$ 而没有记录 $k$ 的值。虽然这其实不是什么致命的问题，但是在萱萱告诉花花她这个疏漏时，作为完美主义者的花花还是恳求萱萱帮她修正 $M_k$ 的值。萱萱便把这个任务交给了她的AI——你。

样例输入 1

10
1 1 1 0 0 1 1 1 0 0 
1 1 1 0 0 0 0 0 1 1 
0
100

样例输出 1

0101111001

样例输入 2

10
1 1 1 0 0 1 1 1 0 0 
1 1 1 0 0 0 0 0 1 1 
1 
3
0 1 0 1 1 1 1 1 0 1 

样例输出 2

0101111001