P5885 [CTSC2014] Random Numbers

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

- 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.

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).

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