毒蛇の脱走 (Snake Escaping)

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

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

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

• \(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 点]

• 追加の制限はない．

JOI 2018 · JCIOI · CC BY-SA 4.0