3557 - [Ctsc2014]随机数
露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是，有计算机生成的随机数序列并非真正的随机数， 而是由一定法则生成的伪随机数。 某一天，露露了解了一种生成随机数的方法，成为Mersenne twister。给定初始参数m∈Z+，x∈Z+∩[0,2m)和初值M0∈Z+∩[0,2m)， 它通过下列递推式构造伪随机数列{Mn}:
其中XOR是二进制异或运算（C/C++中的^运算）。而参数x的选取若使得该数列在长度趋于无穷时，近似等概率地在Z+∩(0,2m)中取值， 就称x为好的。例如，在m>1时x=0就显然不是好的。 在露露向伙伴们介绍了Mersenne twister之后，花花想用这一些经典的随机性测试来检验它的随机性强度。为此，花花使用计算机计算 了一些Mk。 但细心的萱萱注意到，花花在某次使用二进制输入k时，在末尾多输入了l个0,。她正想告诉花花这个疏忽，然而花花已经计算并记录了 错误的Mk而没有记录k的值。虽然这其实不是什么致命的问题，但是在萱萱告诉花花她这个疏漏时，作为完美主义者的花花还是恳求萱萱 帮她修正Mk的值。萱萱便把这个任务交给了她的AI——你。
Input
第一行包含一个正整数m， 第二行为二进制表示的x（共m个数，从低位到高位排列） 第三行为二进制表示的M0（排列方式同x）， 第四行包含一个整数type。 接下来分为两种可能的情况： 1.type=0（萱萱记下了花花的输入）：则第五行包含一个整数，表示萱萱记下来的正确的k值。 2.type=1（萱萱未能记下花花的输入）：则第五行为l，第六行输入花花计算出错误的二进制表示的Mk。
Output
仅一行，为m位的01串，表示你求得的正确Mk（同样要求从低位到高位）。
Examples
Input
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 100
Output
0101111001
Hint
M<=1000000 K<=10^6