JOI 研究所の毒蛇

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$以下の整数値が定まっています。長さ$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$ 行目には、整数 $L, Q$ が空白を区切りとして書かれています。これらは順に、毒蛇の部分の個数と、苦情の寄せられる日数を表します。
• $2$ 行目には、長さ $2^L$ の文字列 $S$ が書かれています。この文字列は毒蛇の毒性を表します。
• 続く $Q$ 行のうちの $d$ 行目 ($1 \leqq d \leqq Q$) には、長さ $L$ の文字列 $T_d$ が書かれています。この文字列は $d$ 日目の苦情を表します。

出力

標準出力に $Q$ 行で出力してください。$d$ 行目には、$d$ 日目に脱走した可能性のある毒蛇の毒性の合計を表す整数を出力してください。

制約