RNA 가닥 팔기

재현이는 'A', 'G', 'C', 'U' 네 글자만 안다. 심심해하는 재현이를 위해 현수가 문제를 하나 냈다.

현수의 사전에는 문자열 N개가 들어 있고, 재현이는 질문 M개에 답해야 한다. 질문 하나는 문자열 P와 Q로 이루어진다. 사전에 있는 N개의 문자열 중에서 접두사가 P이면서 접미사가 Q인 문자열이 몇 개인지 세어 출력하면 된다.

사전에 있는 문자열을 세는 것이므로 각 질문의 답은 0 이상 N 이하다. 한 문자열 안에서 접두사 P가 차지하는 구간과 접미사 Q가 차지하는 구간이 겹쳐도 된다.

첫째 줄에 사전에 있는 문자열의 수 N과 질문의 수 M이 공백으로 구분되어 주어진다. ($1 \le N, M \le 2 \times 10^6$)

둘째 줄부터 N개 줄에 사전에 있는 문자열이 한 줄에 하나씩 주어진다.

그다음 M개 줄에 질문마다 문자열 P와 Q가 공백으로 구분되어 주어진다.

사전에 있는 문자열과 P, Q는 모두 'A', 'G', 'C', 'U'로만 이루어지고, 각각의 길이는 $10^5$ 이하다. 사전에 있는 문자열의 길이 합, P의 길이 합, Q의 길이 합은 각각 $2 \times 10^6$ 이하다.

M개 줄에 각 질문의 답을 입력에 주어진 순서대로 출력한다.