Hamako Online Judge

TLE
2sec

MLE
64MB

得点
100

毒蛇の脱走(Snake Escaping)

JOI 研究所では2^L 匹の毒蛇を飼っており，それぞれ0, 1, ..., 2^L - 1 の番号が付けられている．すべての毒蛇は頭から順にL 個の部分に分かれており，それぞれの部分は青または赤である．毒蛇i に対し，i を2進表記してi = $\sum_{k=1}^{L}$ c_k2^{L-k} (0 \leq c_k \leq 1) とおいたとき，

c_k = 0 であれば，毒蛇i の頭から数えてk 番目の部分は青であり，
c_k = 1 であれば，毒蛇i の頭から数えてk 番目の部分は赤である．

各毒蛇には毒性と呼ばれる0 以上9 以下の整数値が定まっている．0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる長さ2^L の文字列S が与えられ，そのi 文字目(1 \leq i \leq 2^L) は毒蛇i - 1 の毒性を表す．

毒蛇たちの動きは素早いので，JOI 研究所からは，よく毒蛇たちが脱走してしまう．JOI 研究所には脱走した毒蛇を目撃した周辺住民から苦情が寄せられる．

あなたには，Q 日間にわたる苦情の情報が与えられる．d 日目(1 \leq d \leq Q) に寄せられた苦情は， 0, 1, ?からなる長さL の文字列T_d として表され，

T_d のj 文字目(1 \leq j \leq L) が0 の場合は，d 日目に脱走したすべての毒蛇の頭から数えてj 番目の部分が青であることを表し，
T_d のj 文字目(1 \leq j \leq L) が1 の場合は，d 日目に脱走したすべての毒蛇の頭から数えてj 番目の部分が赤であることを表し，
T_d のj 文字目(1 \leq j \leq L) が? の場合は，d 日目に脱走した毒蛇の頭から数えてj 番目の部分については，周辺住民からは情報が与えられなかったことを表す．

苦情はすべて正確な情報である．脱走した毒蛇はJOI 研究所の職員がその日のうちに捕獲する．捕獲された毒蛇が，翌日以降に再び脱走することはあり得る．

毒蛇の脱走によるリスクを見積もるために，JOI 研究所のK 理事長は脱走した可能性のある毒蛇の毒性の合計を知りたい．あなたの仕事は，Q 日間にわたる苦情の情報から，それぞれの日ごとに，その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成することである．

課題

毒蛇の毒性を表す文字列S と，Q 日間の苦情の情報が与えられるので，それぞれの日ごとに，その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成せよ．

メモリ制限が小さいことに注意すること．

入力

標準入力から以下の入力を読み込め．

1 行目には，整数L, Q が空白を区切りとして書かれている．これらは順に，毒蛇の部分の個数と，苦情の寄せられる日数を表す．
2 行目には，長さ2^L の文字列S が書かれている．この文字列は毒蛇の毒性を表す．
続くQ 行のうちのd 行目(1 \leq d \leq Q) には，長さL の文字列T_d が書かれている．この文字列はd 日目の苦情を表す．

出力

標準出力にQ 行で出力せよ．d 行目には，d 日目に脱走した可能性のある毒蛇の毒性の合計を表す整数を出力せよ．

制限

すべての入力データは以下の条件を満たす．

1 \leq L \leq 20．
1 \leq Q \leq 1 000 000．
S は長さ2^L の文字列である．
文字列S は0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる．
T_d は長さL の文字列である(1 \leq d \leq Q)．
文字列T_d は0, 1, ? からなる(1 \leq d \leq Q)．

小課題

小課題 1 [5 点]

　以下の条件を満たす．

L ≦ 10.
Q ≦ 1000.

小課題2 [7 点]

L ≦ 10 を満たす．

小課題3 [10 点]

L ≦ 13 を満たす．

小課題4 [53 点]

Q ≦ 50000 を満たす．

小課題5 [25 点]

追加の制限はない．

入出力例

入力例1

3 5
12345678
000
0??
1?0
?11
???

出力例1

この入力例では，L = 3 である．3 つの部分に分かれた毒蛇が，全部で2^3 = 8 匹いる．苦情は5 日間にわたって寄せられる．

1 日目に脱走した可能性のある毒蛇は，毒蛇0 のみである．毒性の合計は1 である．
2 日目に脱走した可能性のある毒蛇は，毒蛇0, 1, 2, 3 である．毒性の合計は10 である．
3 日目に脱走した可能性のある毒蛇は，毒蛇4, 6 である．毒性の合計は12 である．
4 日目に脱走した可能性のある毒蛇は，毒蛇3, 7 である．毒性の合計は12 である．
5 日目に脱走した可能性のある毒蛇は，毒蛇0, 1, 2, 3, 4, 5, 6, 7 である．毒性の合計は36 である．

入力例2

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

出力例2

005 - 毒蛇の脱走(Snake Escaping)