露露、花花和萱萱最近對電腦中的隨機數產生了興趣。眾所周知，由電腦產生的隨機數序列並非真正的隨機數，而是按照一定規則產生的偽隨機數。

某一天，露露了解了一種稱為 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)$ 中取值，就稱 $x$ 是好的。例如，當 $m>1$ 時，$x=0$ 顯然不是好的。

露露向夥伴們介紹 Mersenne twister 之後，花花想用一些經典的隨機性測試來檢驗它的隨機性強度。為此，花花使用電腦計算了一些 $M_k$。

但細心的萱萱注意到，花花某次使用二進位輸入 $k$ 時，在末尾多輸入了 $l$ 個 0。她正想告訴花花這個疏忽，然而花花已經計算並記錄了錯誤的 $M_k$ 值，卻沒有記錄 $k$。雖然這其實不是什麼致命的問題，但當萱萱告訴花花這個疏漏時，身為完美主義者的花花仍懇求萱萱幫他修正 $M_k$ 的值。萱萱便把這個任務交給了她的AI——你。

輸入格式

輸入檔案 random.in 的第一行包含一個正整數 $m$，第二行是以二進位表示的 $x$（共 $m$ 個數，從低位到高位排列），第三行是以二進位表示的 $M_0$（排列方式與 $x$ 相同），第四行包含一個整數 $type$。

接下來分為兩種可能的情況：

1. $type=0$（萱萱記下了花花的輸入）：第五行包含一個整數，表示萱萱記下的正確 $k$ 值。

2. $type=1$（萱萱未能記下花花的輸入）：第五行為 $l$，第六行輸入花花計算出的錯誤 $M_k$，以二進位表示。

輸出格式

輸出檔案 random.out 只有一行，是一個 $m$ 位的 01 字串，表示你求得的正確 $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。

資料範圍