Лулу, Хуахуа та Сюаньсюань останнім часом зацікавилися випадковими числами в комп’ютерах. Як відомо, послідовності випадкових чисел, які генерує комп’ютер, насправді не випадкові, а є псевдовипадковими числами, утвореними за певними правилами.
Одного дня Лулу дізналася про спосіб генерації випадкових чисел під назвою 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)\mathbin{\mathrm{xor}}x,&2M_{n-1}\ge 2^m.\end{cases}$$
Тут $\mathrm{xor}$ — побітове виключне АБО (операція ^ у C/C++). Якщо параметр $x$ обрано так, що зі зростанням довжини послідовності до нескінченності її значення наближено рівноймовірно розподілені в $\mathbb Z\cap(0,2^m)$, то $x$ називають хорошим. Наприклад, при $m>1$ значення $x=0$ очевидно не є хорошим.
Після того як Лулу розповіла друзям про Mersenne twister, Хуахуа вирішив перевірити його випадковість за допомогою класичних тестів. Для цього він обчислив на комп’ютері деякі значення $M_k$.
Але уважна Сюаньсюань помітила, що одного разу, вводячи $k$ у двійковому вигляді, Хуахуа дописав у кінці зайві $l$ нулів. Вона хотіла повідомити йому про помилку, однак він уже обчислив і записав неправильне значення $M_k$, не зберігши значення $k$. Хоча ця проблема й не була критичною, після розповіді Сюаньсюань перфекціоніст Хуахуа все ж попросив її допомогти виправити $M_k$. Сюаньсюань доручила це своєму штучному інтелекту — вам.
Вхідні дані
Перший рядок вхідного файла random.in містить додатне ціле число $m$. Другий рядок містить двійкове подання $x$: $m$ чисел, від молодшого біта до старшого. Третій рядок містить двійкове подання $M_0$ у такому самому порядку, а четвертий — ціле число $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 | $\le 10$ | $\le 10^9$ | N/A | $0$ | Так |
| 2 | $\le 10$ | $\le 10^9$ | $\le 10$ | $1$ | Так |
| 3 | $\le 100$ | $\le 10^9$ | N/A | $0$ | Так |
| 4 | $\le 100$ | $\le 10^9$ | N/A | $0$ | Так |
| 5 | $\le 100$ | $\le 10^9$ | N/A | $0$ | Так |
| 6 | $\le 100$ | $\le 10^5$ | $=1$ | $1$ | Так |
| 7 | $\le 100$ | $\le 10^9$ | $\le 10$ | $1$ | Так |
| 8 | $\le 100$ | $\le 10^9$ | $\le 10$ | $1$ | Так |
| 9 | $\le 100$ | $\le 10^9$ | $\le 10$ | $1$ | Так |
| 10 | $\le 1000$ | $\le 10^{18}$ | $\le 10$ | $1$ | Так |
| 11 | $\le 1000$ | $\le 10^{18}$ | $\le 10$ | $1$ | Так |
| 12 | $\le 1000$ | $\le 10^{18}$ | $\le 10$ | $1$ | Так |
| 13 | $\le 2000$ | $\le 10^9$ | N/A | $0$ | Так |
| 14 | $\le 2000$ | $\le 10^9$ | N/A | $0$ | Так |
| 15 | $\le 500000$ | $\le 10^6$ | N/A | $0$ | Ні |
| 16 | $\le 500000$ | $\le 10^6$ | N/A | $0$ | Ні |
| 17 | $\le 1000000$ | $\le 10^6$ | N/A | $0$ | Ні |
| 18 | $\le 1000000$ | $\le 10^6$ | N/A | $0$ | Ні |
| 19 | $\le 1000000$ | $\le 10^6$ | N/A | $0$ | Ні |
| 20 | $\le 1000000$ | $\le 10^6$ | N/A | $0$ | Ні |