CODE

题号：NC237514
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Galen made an original communication device . The device can send a string of length $2^n-1$ with only digits $0$ or $1$ .

Unfortunately , due to the interference of the signal , each bit maybe wrong with probability $\frac {1}{10^{20}}$ .

Galen is very confused about this . In order to solve this problem, he designed such an algorithm .

We define the $i-th(1\leq i \leq 2^n-1)$ digit he sent as $s[i]$ .

For each $i(i=2^k)$ , $s[i]$ satisfied $s[i]=\bigoplus(s[j]),j\&i=i$ , it means $s[i]$ equals to the xor sum of all position $j$ which $k-th$ digit is 1 in binary representation .

Such as $s[3]=1,s[5]=1,s[6]=0,s[7]=1$ ，then

$s[1]=s[3] \bigoplus s[5]\bigoplus s[7]=1$ ，

$s[2]=s[3]\bigoplus s[6]\bigoplus s[7]=0$ ，

$s[4]=s[5]\bigoplus s[6] \bigoplus s[7]=0$ 。

The final message to be sent is $1010101$ 。

Now , Galen receives a message from the device , but he is not sure if it was the origin message . Please help him find the origin message . You can assume that the message he received has at most one digit wrong .

输入描述:

The first line contains two positive integer  .

Then  line follows , each line contains a  string with length  .

输出描述:

For each case , print an string indicates the answer .

示例1

输入

复制

输出

复制

1010101
1010101
1010101