Problem Description

Lulu, Huahua, and Xuanxuan have recently become interested in random numbers in computers. As is well known, random number sequences generated by computers are not truly random; they are pseudorandom numbers produced by certain rules.

One day, Lulu learned a method for generating random numbers called the Mersenne twister. Given initial parameters $m \in Z+$, $x \le Z+\cap[0,2m)$ and an initial value $M_0 \in Z+\cap [0,2m)$, it constructs a pseudorandom sequence $\{M_n\}$ by the following recurrence:

$$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}$$

Here, $XOR$ is the bitwise exclusive OR operation (the ^ operator in C/C++). If the choice of parameter $x$ makes the sequence, as its length tends to infinity, take values in $Z+ \cap (0,2m)$ approximately with equal probability, then $x$ is called good. For example, when $m>1$, $x=0$ is obviously not good.

After Lulu introduced the Mersenne twister to her partners, Huahua wanted to use some classic randomness tests to check its randomness strength. For this, Huahua used a computer to compute some $M_k$.

But careful Xuanxuan noticed that when Huahua entered $k$ in binary, she accidentally typed $l$ extra $0$’s at the end. Xuanxuan was about to tell Huahua about this mistake, but Huahua had already computed and recorded the wrong $M_k$ without recording the value of $k$. Although this is not a fatal problem, when Xuanxuan told Huahua about the oversight, the perfectionist Huahua still begged Xuanxuan to help her correct the value of $M_k$. Xuanxuan then handed this task to her AI—you.

Input Format

• The first line contains a positive integer $m$.
• The second line is the binary representation of $x$ (a total of $m$ bits, arranged from low bit to high bit).
• The third line is the binary representation of $M_0$ (arranged in the same way as $x$).
• The fourth line contains an integer $type$.

Next, there are two possible cases:

1. $type=0$ (Xuanxuan recorded Huahua’s input): the fifth line contains an integer, meaning the correct value of $k$ that Xuanxuan recorded.
2. $type=1$ (Xuanxuan failed to record Huahua’s input): the fifth line is $l$, and the sixth line gives the wrong binary representation of $M_k$ computed by Huahua.

Output Format

Only one line: an $m$-bit 01 string, representing the correct $M_k$ you computed (also required to be from low bit to high bit).

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

0101111001

Hint

For the part with $type=0$, either $m,k \le 10^6$, or $m \le 2000,k \le 10^{18}$.

For the part with $type=1$, $m \le 10^3$, $k \le 10^{18}$, $l \le 10$, and $x$ is good.

Translated by ChatGPT 5