露露、花花、萱萱は最近、コンピュータの乱数に興味を持ちました。よく知られているように、コンピュータが生成する乱数列は真の乱数ではなく、一定の規則によって生成される疑似乱数です。

ある日、露露は 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 の 1 行目は正整数 $m$、2 行目は二進数で表した $x$（全部で $m$ 個の数を下位ビットから上位ビットの順に並べたもの）、3 行目は二進数で表した $M_0$（$x$ と同じ順序）、4 行目は整数 $type$ です。

以降は次の 2 通りに分かれます。

1. $type=0$（萱萱が花花の入力を記録していた場合）：5 行目は、萱萱が記録した正しい $k$ の値を表す整数です。
2. $type=1$（萱萱が花花の入力を記録できなかった場合）：5 行目は $l$、6 行目は花花が計算した誤った $M_k$ の二進数表現です。

出力

出力ファイル random.out は 1 行だけとし、求めた正しい $M_k$ を表す長さ $m$ の 01 文字列を出力してください（同様に、下位ビットから上位ビットの順に並べます）。

入出力例

入力 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 を参照してください。

制約