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) とおいたとき,
各毒蛇には毒性と呼ばれる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 として表され,
苦情はすべて正確な情報である.脱走した毒蛇はJOI 研究所の職員がその日のうちに捕獲する.捕獲された毒蛇が,翌日以降に再び脱走することはあり得る.
毒蛇の脱走によるリスクを見積もるために,JOI 研究所のK 理事長は脱走した可能性のある毒蛇の毒性の合計を知りたい.あなたの仕事は,Q 日間にわたる苦情の情報から,それぞれの日ごとに,その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成することである.
毒蛇の毒性を表す文字列S と,Q 日間の苦情の情報が与えられるので,それぞれの日ごとに,その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成せよ.
メモリ制限が小さいことに注意すること.
標準入力から以下の入力を読み込め.
標準出力にQ 行で出力せよ.d 行目には,d 日目に脱走した可能性のある毒蛇の毒性の合計を表す整数を出力せよ.
すべての入力データは以下の条件を満たす.
3 5 12345678 000 0?? 1?0 ?11 ???
1 10 12 12 36
この入力例では,L = 3 である.3 つの部分に分かれた毒蛇が,全部で2^3 = 8 匹いる.苦情は5 日間にわたって寄せられる.
4 8 3141592653589793 0101 ?01? ??1? ?0?? 1?00 01?1 ??10 ????
9 18 38 30 14 15 20 80
情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』