P5885 [CTSC2014] 随机数

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是，有计算机生成的随机数序列并非真正的随机数，而是由一定法则生成的伪随机数。 某一天，露露了解了一种生成随机数的方法，称为 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}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（同样要求从低位到高位）。

对于 $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$ 是“好的”。