008 - 石版

時間制限 5 秒 / メモリ制限 256 MB / 得点 15 / x 3 /


TLE
5sec
MLE
256MB
得点
15

古代国家イワシロの遺跡から無数の石版が発見された。研究者の調査によって、各石版には一つの単語が刻まれていることが分かった。しかし、長年の風化によって、以下の理由で解読が困難な石版もあるようだ。

  • 石版に書かれている単語の一つの文字だけが 苔で覆われている場合があり、その文字を把握することができない。
  • 石版の左側が欠けており、そこに何か文字列が書かれていたかもしれない(石版の左側0文字以上を把握することができない)。
  • 石版の右側が欠けており、そこに何か文字列が書かれていたかもしれない(石版の右側0文字以上を把握することができない)。

石版に苔が生えている場所は多くても一か所しかない。また、欠けた石版に苔が生えていることはあるが、石版の両側が同時に欠けていることはない。

研究者は、石版発見以前の調査でわかっている単語をまとめた辞書を持っている。しかし、風化の影響による苔と欠けがある石版から元の単語を推測したとき、辞書の中の単語に当てはまるものがいくつあるか、すぐには分からない。

課題

石版の情報が与えられたとき、与えられた辞書の中に当てはまりそうな単語がいくつあるかを数えるプログラムを作成せよ。

入力

入力は以下の形式で与えられる

N M 
word1
word2
: 
wordN
slate1
slate2
: 
slateM

1行目に辞書に載っている単語の数N(1≦N≦50000)、石版の数M(1≦M≦50000)が与えられる。続くN行に単語wordiが与えられる。単語は英小文字のみを含む長さが1以上200以下の文字列である。ただし、N個の単語は全て異なる。続くM行に、各石版の情報を表す文字列slateiが与えられる。slateiは英小文字、「?」 、「*」 を含む長さが1以上200以下の文字列である。?は苔に覆われた文字を表す。?は一つの文字列に、多くとも一つしか現れない。文字列の先頭が*の場合、石版の左側が欠けていることを示す。文字列の末尾が*の場合、石版の右側が欠けていることを示す。*は、文字列の先頭か末尾以外には現れず、同時に両側に現れることはない。*が一つだけの文字列が与えられることはない。

入力で与えられる文字列の文字の総数は 3000000 を超えない。

時間制限

入力に対して、実行時間が10秒を超えてはならない。

出力

各石版について、単語の数を1行に出力する。

入出力例

入力例1

5 4
aloe
apple
apricot
cactus
cat
apple
ap*
*e
ca?*

出力例1

1
2
2
2