화장실 단말기

Smith는 더럽고 사용되지 않는 화장실 한쪽에서 깨어나며, 그의 발목은 파이프에 사슬로 묶여 있다. 그의 옆에는 손으로 쓴 메시지 "Play Me"가 붙은 테이프 플레이어가 있다. 그는 자신의 뒷주머니에서 테이프를 발견한다. 테이프를 테이프 플레이어에 넣은 뒤, 그는 천장에 매달린 열쇠를 보게 된다. 열쇠는 어떤 기계에 사슬로 연결되어 있으며, 그 기계는 그의 옆에 있는 단말기에 연결되어 있다. 재생 버튼을 누르자 테이프에서 거친 목소리가 흘러나오기 시작한다:

"잘 들어라, Smith. 보다시피 너는 상당히 곤란한 상황에 처해 있으며, 탈출하려면 퍼즐을 풀어야 한다.

단어를 나타내는 N개의 문자열이 주어진다. 각 단어는 최대 length L이고 문자 'a'-'e'로 이루어진다. 패턴을 나타내는 M개의 문자열도 주어진다. 패턴은 length ≤ L인 문자열이며, 문자 'a'-'e'와 최대 3개의 문자 '?'로 이루어진다. 문자 '?'는 알 수 없는 문자로, 임의의 문자 'a'-'e'와 같을 수도 있고 빈 문자일 수도 있다. 각 패턴에 대해 주어진 패턴과 일치하는 단어의 수를 구하여라. 문제를 풀고 결과를 단말기에 입력하면 열쇠가 천장에서 떨어지고 너는 탈출할 수 있다. 게임을 시작하지."

Help Smith 탈출한다.

입력의 첫 번째 줄에는 단어와 패턴의 수를 각각 나타내는 두 정수 N and M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 5000)가 주어진다.

다음 N개의 줄에는 각 단어가 주어지고, 그 N개의 줄 다음에 이어지는 M개의 줄에는 각 패턴이 주어진다. 각 단어와 각 패턴은 최대 length L (1 ≤ L ≤ 50)이다. 각 패턴에는 문자 '?'가 세 개 이하로 포함된다. 단어와 패턴의 나머지 모든 문자는 'a'부터 'e'까지의 소문자 영어 알파벳이다.

출력은 M개의 줄로 이루어지며, 각 줄에는 해당 패턴과 일치하는 단어의 수를 나타내는 정수 하나를 출력한다.

'?'를 각각 'b', 'e', 빈 문자로 바꾸면 'abc', 'aec', 'ac'를 얻는다.