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

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

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

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

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

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

課題

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

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

制限

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

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

小課題

小課題 1 [5 点]

以下の条件を満たす．

• L \leqq 10．
• Q \leqq 1 000．

小課題 2 [7 点]

• L \leqq 10 を満たす．

小課題 3 [10 点]

• L \leqq 13 を満たす．

小課題 4 [53 点]

• Q \leqq 50 000 を満たす．

小課題 5 [25 点]

• 追加の制限はない．

入力例 1

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

出力例 1

1
10
12
12
36

この入力例では，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

9
18
38
30
14
15
20
80