問題文

あなたは以下のようなゲームを行うことにしました。

• ゲームの開始時にあなたは非負整数 $T$ を持っており、スコアは $0$ である。
• 長さ $N$ の数列 $A$ を用いて以下の操作を $N$ 回繰り返す。
• $i$ 回目の操作では、現在持っている整数を $X$ として、$X$ を以下のどちらかに変化させる。
• $X$ と $A_i$ の bitwise and
• $X$ と $A_i$ の bitwise or
• 各操作後に、スコアが $|(\mathrm{変}\mathrm{化}\mathrm{後}\mathrm{の}X)-(\mathrm{変}\mathrm{化}\mathrm{前}\mathrm{の}X)|$ 増加する。

• $i$ 番目のクエリでは、初期値 $T=t_i$ であり、操作手順 $S$ に従って操作を行った時の $N$ 回の操作後のスコアを求める。

入力

$NQ$
$A_1{A}_2\dots A_N$
$S$
$t_1{t}_2\dots t_Q$

• $1\le N,Q\le {10}^5$
• $0\le A_i\le {10}^9$
• $S$ は0と1からなる長さ $N$ の文字列である。
• $S$ の $i$ 文字目が0である場合、$i$ 回目の操作で bitwise and を選択する。
  $S$ の $i$ 文字目が1である場合、$i$ 回目の操作で bitwise or を選択する。
• $0\le t_i\le {10}^9$

出力

$i$ 行目には $i$ 番目のクエリの答えを出力してください。 最後に改行してください。

サンプル

2 2
2 1
01
1 2

2
1

4 3
0 0 0 0
1111
1 2 3

0
0
0

6 7
8 24 31 25 8 25
010100
18 28 9 5 31 0 21

60
54
35
47
57
42
63