Lulu, Huahua, dan Xuanxuan belakangan ini tertarik pada bilangan acak di komputer. Seperti yang diketahui umum, barisan bilangan acak yang dihasilkan komputer bukanlah bilangan yang benar-benar acak, melainkan bilangan acak semu yang dihasilkan menurut aturan tertentu.

Suatu hari, Lulu mempelajari sebuah metode pembangkitan bilangan acak yang disebut Mersenne twister. Diberikan parameter awal $m\in\mathbb{Z}^+$, $x\in\mathbb{Z}\cap[0,2^m)$, serta nilai awal $M_0\in\mathbb{Z}\cap[0,2^m)$, metode ini membentuk barisan bilangan acak semu $\{M_n\}$ dengan relasi rekurensi berikut:

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

Di sini, $\operatorname{xor}$ adalah operasi XOR biner (operasi ^ dalam C/C++). Jika pemilihan parameter $x$ membuat nilai barisan ini mendekati distribusi seragam pada $\mathbb{Z}\cap(0,2^m)$ ketika panjang barisan menuju tak hingga, maka $x$ disebut baik. Sebagai contoh, ketika $m>1$, jelas bahwa $x=0$ tidak baik.

Setelah Lulu memperkenalkan Mersenne twister kepada teman-temannya, Huahua ingin menguji tingkat keacakannya menggunakan beberapa pengujian keacakan klasik. Untuk itu, Huahua menghitung beberapa nilai $M_k$ menggunakan komputer.

Namun, Xuanxuan yang teliti menyadari bahwa suatu kali, ketika Huahua memasukkan $k$ dalam biner, ia menambahkan $l$ angka nol di bagian akhir. Xuanxuan hendak memberitahukan kekeliruan ini, tetapi Huahua sudah menghitung dan mencatat nilai $M_k$ yang salah tanpa mencatat nilai $k$. Meskipun hal ini sebenarnya bukan masalah fatal, ketika Xuanxuan memberitahukan kelalaiannya, Huahua yang perfeksionis tetap memohon kepada Xuanxuan untuk membantunya memperbaiki nilai $M_k$. Xuanxuan pun menyerahkan tugas ini kepada AI miliknya—kamu.

Masukan

Baris pertama berkas masukan random.in berisi sebuah bilangan bulat positif $m$. Baris kedua berisi representasi biner $x$, terdiri dari $m$ angka yang diurutkan dari bit terendah ke bit tertinggi. Baris ketiga berisi representasi biner $M_0$, dengan urutan yang sama seperti $x$. Baris keempat berisi sebuah bilangan bulat $type$.

Selanjutnya terdapat dua kemungkinan:

1. $type=0$ (Xuanxuan mencatat masukan Huahua): baris kelima berisi sebuah bilangan bulat, yaitu nilai $k$ yang benar yang dicatat Xuanxuan.
2. $type=1$ (Xuanxuan tidak berhasil mencatat masukan Huahua): baris kelima berisi $l$, dan baris keenam berisi representasi biner nilai $M_k$ yang salah yang dihitung Huahua.

Keluaran

Berkas keluaran random.out hanya berisi satu baris, berupa string 01 sepanjang $m$ bit yang menyatakan nilai $M_k$ yang benar yang kamu peroleh. Urutannya juga harus dari bit terendah ke bit tertinggi.

Contoh

Masukan 1

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

Keluaran 1

0101111001

Masukan 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

Keluaran 2

0101111001

Contoh 3

Lihat random/random.in dan random/random.ans di direktori peserta.

Batasan