露露, 花花 и 萱萱 недавно заинтересовались случайными числами в компьютерах. Как известно, последовательности, генерируемые компьютером, не являются по-настоящему случайными: это псевдослучайные числа, полученные по определённым правилам.
Однажды 露露 узнала о методе генерации случайных чисел под названием Mersenne twister. Для начальных параметров $m\in\mathbb Z^+$, $x\in\mathbb Z\cap[0,2^m)$ и начального значения $M_0\in\mathbb Z\cap[0,2^m)$ он строит псевдослучайную последовательность $\{M_n\}$ по рекуррентной формуле:
$$M_n=\begin{cases}2M_{n-1},&2M_{n-1}<2^m,\\(2M_{n-1}-2^m)\operatorname{xor}x,&2M_{n-1}\ge2^m.\end{cases}$$
Здесь $\operatorname{xor}$ — побитовое исключающее ИЛИ, операция ^ в C/C++. Параметр $x$ называется хорошим, если при стремлении длины последовательности к бесконечности её значения приблизительно равновероятно распределяются по $\mathbb Z\cap(0,2^m)$. Например, при $m>1$ значение $x=0$ очевидно не является хорошим.
После того как 露露 рассказала друзьям о Mersenne twister, 花花 захотел проверить его случайность классическими статистическими тестами. Для этого он вычислил на компьютере несколько значений $M_k$.
Но внимательная 萱萱 заметила, что однажды, вводя $k$ в двоичной записи, 花花 случайно добавил в конце $l$ нулей. Она хотела сообщить ему об ошибке, однако он уже вычислил и записал неверное значение $M_k$, не сохранив само $k$. Хотя это и не было серьёзной проблемой, 花花, будучи перфекционистом, узнав об ошибке, попросил 萱萱 помочь исправить значение $M_k$. А она поручила эту задачу своему искусственному интеллекту — вам.
Входные данные
Первая строка файла random.in содержит положительное целое число $m$. Вторая строка содержит двоичное представление $x$: $m$ чисел, расположенных от младшего бита к старшему. Третья строка содержит двоичное представление $M_0$ в том же порядке, что и $x$. Четвёртая строка содержит целое число $type$.
Далее возможны два случая:
- $type=0$: 萱萱 запомнила введённое 花花 значение. Пятая строка содержит целое число — правильное значение $k$, записанное 萱萱.
- $type=1$: 萱萱 не смогла запомнить введённое значение. Пятая строка содержит $l$, а шестая — двоичное представление ошибочного значения $M_k$, вычисленного 花花.
Выходные данные
Файл random.out должен содержать одну строку из $m$ символов 0 и 1, представляющую найденное правильное значение $M_k$, также от младшего бита к старшему.
Примеры
Входные данные 1
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 100
Выходные данные 1
0101111001
Входные данные 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
Выходные данные 2
0101111001
Пример 3
См. файлы random/random.in и random/random.ans в каталоге участника.
Ограничения
| Номер теста | $m$ | $k$ | $l$ | $type$ | Является ли $x$ хорошим |
|---|---|---|---|---|---|
| $1$ | $\le10$ | $\le10^9$ | Неприменимо | $0$ | Да |
| $2$ | $\le10$ | $\le10^9$ | $\le10$ | $1$ | Да |
| $3$ | $\le100$ | $\le10^9$ | Неприменимо | $0$ | Да |
| $4$ | $\le100$ | $\le10^9$ | Неприменимо | $0$ | Да |
| $5$ | $\le100$ | $\le10^9$ | Неприменимо | $0$ | Да |
| $6$ | $\le100$ | $\le10^5$ | $=1$ | $1$ | Да |
| $7$ | $\le100$ | $\le10^9$ | $\le10$ | $1$ | Да |
| $8$ | $\le100$ | $\le10^9$ | $\le10$ | $1$ | Да |
| $9$ | $\le100$ | $\le10^9$ | $\le10$ | $1$ | Да |
| $10$ | $\le1000$ | $\le10^{18}$ | $\le10$ | $1$ | Да |
| $11$ | $\le1000$ | $\le10^{18}$ | $\le10$ | $1$ | Да |
| $12$ | $\le1000$ | $\le10^{18}$ | $\le10$ | $1$ | Да |
| $13$ | $\le2000$ | $\le10^9$ | Неприменимо | $0$ | Да |
| $14$ | $\le2000$ | $\le10^9$ | Неприменимо | $0$ | Да |
| $15$ | $\le500000$ | $\le10^6$ | Неприменимо | $0$ | Нет |
| $16$ | $\le500000$ | $\le10^6$ | Неприменимо | $0$ | Нет |
| $17$ | $\le1000000$ | $\le10^6$ | Неприменимо | $0$ | Нет |
| $18$ | $\le1000000$ | $\le10^6$ | Неприменимо | $0$ | Нет |
| $19$ | $\le1000000$ | $\le10^6$ | Неприменимо | $0$ | Нет |
| $20$ | $\le1000000$ | $\le10^6$ | Неприменимо | $0$ | Нет |