露露、花花同萱萱最近對電腦入面嘅隨機數產生咗興趣。大家都知道，電腦產生嘅隨機數序列唔係真正嘅隨機數，而係按照一定規則產生嘅偽隨機數。

有一日，露露認識咗一種叫做 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。

資料範圍同約定