露露, 花花 i 萱萱 zainteresowali się ostatnio liczbami losowymi w komputerach. Jak powszechnie wiadomo, ciągi liczb losowych generowane przez komputer nie są naprawdę losowe, lecz są ciągami pseudolosowymi tworzonymi według określonych reguł.
Pewnego dnia 露露 poznała metodę generowania liczb losowych o nazwie Mersenne twister. Dla parametrów $m\in\mathbb Z^+$, $x\in\mathbb Z\cap[0,2^m)$ oraz wartości początkowej $M_0\in\mathbb Z\cap[0,2^m)$ konstruuje ona ciąg pseudolosowy $\{M_n\}$ za pomocą rekurencji:
$$ M_n=\begin{cases} 2M_{n-1},&2M_{n-1}<2^m,\\ (2M_{n-1}-2^m)\operatorname{xor}x,&2M_{n-1}\ge 2^m. \end{cases} $$
Tutaj $\operatorname{xor}$ oznacza bitową alternatywę wykluczającą (operator ^ w C/C++). Jeżeli wybór parametru $x$ sprawia, że wraz z długością ciągu dążącą do nieskończoności wartości w $\mathbb Z\cap(0,2^m)$ są przyjmowane w przybliżeniu z jednakowym prawdopodobieństwem, nazywamy $x$ dobrym. Na przykład dla $m>1$ wartość $x=0$ oczywiście nie jest dobra.
Gdy 露露 przedstawiła znajomym Mersenne twister, 花花 postanowił sprawdzić jego losowość za pomocą klasycznych testów. W tym celu obliczył na komputerze pewne wartości $M_k$.
Jednak uważna 萱萱 zauważyła, że podczas jednego z wprowadzeń liczby $k$ w zapisie binarnym 花花 dopisał na końcu o $l$ zer za dużo. Chciała mu powiedzieć o pomyłce, ale 花花 zdążył już obliczyć i zapisać błędną wartość $M_k$, nie zapisując wartości $k$. Choć nie jest to szczególnie poważny problem, gdy 萱萱 poinformowała go o błędzie, perfekcjonista 花花 poprosił ją o poprawienie wartości $M_k$. 萱萱 przekazała to zadanie swojej sztucznej inteligencji — tobie.
Wejście
Pierwszy wiersz pliku random.in zawiera dodatnią liczbę całkowitą $m$. Drugi zawiera binarny zapis $x$: łącznie $m$ cyfr, od najmniej do najbardziej znaczącej. Trzeci zawiera binarny zapis $M_0$ w takim samym porządku jak $x$. Czwarty wiersz zawiera liczbę całkowitą $type$.
Dalej możliwe są dwa przypadki:
- $type=0$ (萱萱 zapisała dane wprowadzone przez 花花): piąty wiersz zawiera liczbę całkowitą — poprawną wartość $k$ zapisaną przez 萱萱.
- $type=1$ (萱萱 nie zdołała zapisać danych wprowadzonych przez 花花): piąty wiersz zawiera $l$, a szósty — binarny zapis błędnej wartości $M_k$ obliczonej przez 花花.
Wyjście
Plik random.out powinien zawierać tylko jeden wiersz: ciąg $01$ długości $m$, przedstawiający obliczoną poprawną wartość $M_k$, również od najmniej do najbardziej znaczącego bitu.
Przykład
Wejście 1
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 100
Wyjście 1
0101111001
Wejście 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
Wyjście 2
0101111001
Przykład 3
Zobacz random/random.in i random/random.ans w katalogu zawodnika.
Ograniczenia
| Numer testu | $m$ | $k$ | $l$ | $type$ | Czy $x$ jest dobry |
|---|---|---|---|---|---|
| $1$ | $\le 10$ | $\le 10^9$ | Nie dotyczy | $0$ | Tak |
| $2$ | $\le 10$ | $\le 10^9$ | $\le 10$ | $1$ | Tak |
| $3$ | $\le 100$ | $\le 10^9$ | Nie dotyczy | $0$ | Tak |
| $4$ | $\le 100$ | $\le 10^9$ | Nie dotyczy | $0$ | Tak |
| $5$ | $\le 100$ | $\le 10^9$ | Nie dotyczy | $0$ | Tak |
| $6$ | $\le 100$ | $\le 10^5$ | $=1$ | $1$ | Tak |
| $7$ | $\le 100$ | $\le 10^9$ | $\le 10$ | $1$ | Tak |
| $8$ | $\le 100$ | $\le 10^9$ | $\le 10$ | $1$ | Tak |
| $9$ | $\le 100$ | $\le 10^9$ | $\le 10$ | $1$ | Tak |
| $10$ | $\le 1000$ | $\le 10^{18}$ | $\le 10$ | $1$ | Tak |
| $11$ | $\le 1000$ | $\le 10^{18}$ | $\le 10$ | $1$ | Tak |
| $12$ | $\le 1000$ | $\le 10^{18}$ | $\le 10$ | $1$ | Tak |
| $13$ | $\le 2000$ | $\le 10^9$ | Nie dotyczy | $0$ | Tak |
| $14$ | $\le 2000$ | $\le 10^9$ | Nie dotyczy | $0$ | Tak |
| $15$ | $\le 500000$ | $\le 10^6$ | Nie dotyczy | $0$ | Nie |
| $16$ | $\le 500000$ | $\le 10^6$ | Nie dotyczy | $0$ | Nie |
| $17$ | $\le 1000000$ | $\le 10^6$ | Nie dotyczy | $0$ | Nie |
| $18$ | $\le 1000000$ | $\le 10^6$ | Nie dotyczy | $0$ | Nie |
| $19$ | $\le 1000000$ | $\le 10^6$ | Nie dotyczy | $0$ | Nie |
| $20$ | $\le 1000000$ | $\le 10^6$ | Nie dotyczy | $0$ | Nie |