毒蛇の脱走(Snake Escaping)

毒蛇の毒性を表す文字列S と,Q 日間の苦情の情報が与えられるので,それぞれの日ごとに,その日に
脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成せよ.
メモリ制限が小さいことに注意すること.

第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)

小課題1 [5 点]
以下の条件を満たす.
• L ≦10.
• Q ≦1 000.
小課題2 [7 点]
• L ≦10 を満たす.
小課題3 [10 点]
• L ≦13 を満たす.
小課題4 [53 点]
• Q ≦50 000 を満たす.
小課題5 [25 点]
• 追加の制限はない.

第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)

標準入力から以下の入力を読み込め.
• 1 行目には,整数L, Q が空白を区切りとして書かれている.これらは順に,毒蛇の部分の個数と,苦
情の寄せられる日数を表す.
• 2 行目には,長さ2L の文字列S が書かれている.この文字列は毒蛇の毒性を表す.
• 続くQ 行のうちのd 行目(1 ≦d ≦Q) には,長さL の文字列Td が書かれている.この文字列はd 日
目の苦情を表す.

標準出力にQ 行で出力せよ.d 行目には,d 日目に脱走した可能性のある毒蛇の毒性の合計を表す整数
を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦L ≦20.
• 1 ≦Q ≦1 000 000.
• S は長さ2L の文字列である.
• 文字列S は0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる.
• Td は長さL の文字列である(1 ≦d ≦Q).
• 文字列Td は0, 1, ? からなる(1 ≦d ≦Q).

第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)

생성자가 기록되지 않았습니다.

출처 JOI 2018 Final