기발한 제목

어느 날 의자에 앉아 가장 좋은 정리가 무엇일지 고민했다. 즐겨 쓰는 검색 엔진(Ask Jeeves)을 한 시간쯤 뒤진 끝에 BEST 정리를 찾았다. (BEST 정리는 방향 그래프의 오일러 회로 개수를 구하는 공식이지만, 이 문제에서 그 내용은 필요하지 않다.) BEST라는 이름은 논문 저자인 de Bruijn, van Aardenne-Ehrenfest, Smith, Tutte에서 대문자를 하나씩 따온 것이다.

제목이 기발하다는 말은 이런 뜻이다. 저자를 원하는 순서로 한 줄로 세우고 각 저자의 이름에서 대문자를 하나씩 고른 다음 왼쪽부터 읽었을 때 그 제목이 되면, 그 제목은 기발하다. 따라서 제목의 글자 수는 저자 수와 같아야 한다.

작년에 남태평양 지역 출제진이 어떤 수를 법으로 하는 거듭제곱의 개수에 관한 정리를 증명했고, 여기에 기발한 제목을 붙이려 한다. 출제진의 이름은 Anderson, Best, Cameron-Jones, Corney, French, Guttmann, Haigh, Lobb, Sergeev, Tran, Ward-Graham, Whalan이다. ABCCFGHLSTWW 정리는 각 저자에게서 대문자를 하나씩 가져오기는 했지만, ABCCFGHLSTWW는 올바른 단어가 아니다. (현실에서 올바른 단어는 영어 단어를 뜻하지만, 이 문제에서는 올바른 단어 목록을 입력으로 준다.) 게다가 이름을 어떻게 배열해도 출제진의 대문자로 만들 수 있는 올바른 단어는 하나도 없다. 반면 Anderson, French, Sergeev, Tran 네 명만 정리를 발견했다면 제목을 FAST로 붙일 수 있다(French, Anderson, Sergeev, Tran). 이 네 이름으로 FAST를 만드는 배열은 이것 하나뿐이다. 저자가 Merlin, Oberon, Othello이고 제목을 MOO로 붙이려 한다면 배열은 두 가지다. Merlin, Oberon, Othello 순서와 Merlin, Othello, Oberon 순서다.

보통 논문에 이름을 싣는 순서는 중요하지만, 나는 이미 정년을 보장받았으니 제목을 기발하게 만드는 배열이 몇 가지인지만 세면 된다. 저자 목록과 올바른 제목 목록이 주어진다. 각 제목마다 그 제목을 기발하게 만드는 저자 이름 배열의 개수를 세어라.

첫 줄에 저자 수 $n$ ($1 \le n \le 10$)과 올바른 단어의 개수 $k$ ($1 \le k \le 1000$)가 주어진다.

다음 $n$개 줄에 저자의 이름이 한 줄에 하나씩 주어진다. 이름은 영문 대문자와 소문자로만 이루어지고, 길이는 1 이상 20 이하이며, 대문자가 적어도 하나 들어 있다.

다음 $k$개 줄에 올바른 단어가 한 줄에 하나씩 주어진다. 각 단어는 영문 대문자로만 이루어지고, 길이는 1 이상 20 이하이다.

$k$개의 정수를 한 줄에 하나씩 출력한다. $i$번째 줄에는 $i$번째로 주어진 단어를 제목으로 삼았을 때 그 제목을 기발하게 만드는 저자 이름 배열의 개수를 출력한다.