Lulu, Huahua, and Xuanyuan have recently become interested in random numbers in computers. As is well known, the sequence of random numbers generated by a computer is not truly random, but rather a sequence of pseudo-random numbers generated by a certain rule.

One day, Lulu learned about a method for generating random numbers called the Mersenne twister. Given an initial parameter $m \in \mathbb{Z}^+$, $x \in \mathbb{Z} \cap [0, 2^m)$, and an initial value $M_0 \in \mathbb{Z} \cap [0, 2^m)$, it constructs a pseudo-random sequence $\{M_n\}$ through the following recurrence relation:

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

where $\oplus$ is the binary XOR operation (the ^ operator in C/C++). If the choice of parameter $x$ makes the sequence take values in $\mathbb{Z} \cap [0, 2^m)$ with approximately equal probability as the length tends to infinity, then $x$ is called "good". For example, when $m > 1$, $x = 0$ is clearly not good.

After Lulu introduced the Mersenne twister to her friends, Huahua wanted to use some classic randomness tests to verify its strength. To this end, Huahua used a computer to calculate some $M_k$.

However, the careful Xuanyuan noticed that when Huahua used the binary input $x$ at one point, she accidentally entered $l$ extra $0$s at the end. She was about to tell Huahua about this oversight, but Huahua had already calculated and recorded the incorrect $M_k$ value without recording the value of $x$. Although this is not a fatal problem, when Xuanyuan told Huahua about this oversight, Huahua, being a perfectionist, begged Xuanyuan to help her correct the value of $M_k$. Xuanyuan then handed this task to her AI—you.

Input

The first line contains a positive integer $m$. The second line contains the binary representation of $x$ (a total of $m$ numbers, arranged from the least significant bit to the most significant bit). The third line contains the binary representation of $M_0$ (arranged in the same way as $x$). The fourth line contains an integer $type$.

The following is divided into two possible cases: 1. $type = 0$ (Xuanyuan recorded Huahua's input): The fifth line contains an integer $k$, representing the correct $k$ value recorded by Xuanyuan. 2. $type = 1$ (Xuanyuan failed to record Huahua's input): The fifth line contains $l$, and the sixth line contains the binary representation of the incorrect $M_k$ calculated by Huahua.

Output

Output a single line containing an $m$-bit 01 string, representing the correct $M_k$ you calculated (also required to be arranged from the least significant bit to the most significant bit).

Examples

Input 1

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

Output 1

0101111001

Input 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

Output 2

0101111001

Input 3

See random/random.in and random/random.ans in the contestant directory.

Constraints