题目描述

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

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

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

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

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

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

输入格式

• 第一行包含一个正整数 $m$；
• 第二行为二进制表示的 $x$（共 $m$ 个数，从低位到高位排列）；
• 第三行为二进制表示的 $M_0$（排列方式同 $x$）；
• 第四行包含一个整数 $type$。

接下来分为两种可能的情况：

1. $type=0$（萱萱记下了花花的输入）：则第五行包含一个整数，表示萱萱记下来的正确的 $k$ 值。
2. $type=1$（萱萱未能记下花花的输入）：则第五行为 $l$，第六行输入花花计算出错误的二进制表示的 $M_k$。

输出格式

仅一行，为m位的01串，表示你求得的正确Mk（同样要求从低位到高位）。

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

0101111001

提示

对于 $type=0$ 的部分，要么 $m,k \le 10^6$ 要么 $m\le 2000,k\le 10^{18}$；

对于 $type=1$ 的部分，$m \le 10^3$，$k \le 10^{18}$，$l \le 10$，$x$ 是“好的”。