12898번 - Selling RNA Strands

재현이는 ‘A’, ‘G’, ‘C’, ‘U’ 총 4개의 문자만 압니다. 심심해하는 재현이를 위해 현수는 다음과 같은 문제를 주었습니다. 현수가 가진 사전에 있는 N개의 문자열이 주어졌을 때에 M개의 질문에 대해 대답을 해야 합니다. 각 질문은 2개의 문자열 P와 Q로 구성이 되는데, 사전에 있는 N개의 문자열 중에서 접두사가 P이고 접미사가 Q인 문자열의 개수를 출력해야 합니다. 사전에 있는 문자열들 중 조건을 만족하는 것의 개수를 출력하기 때문에 각 질문에 대한 답은 0 이상 N 이하가 됩니다. 접두사와 접미사는 중복되는 부분이 있어도 무방합니다.

첫째 줄에 사전에 있는 문자열의 수 N과 질문의 수 M이 주어집니다. (1 ≤ N, M ≤ 2,000,000)

둘째 줄부터 N개의 줄에 걸쳐 사전에 있는 문자열들이 한 줄에 하나씩 주어집니다.

N+2번째 줄부터 M개의 줄에 걸쳐 질문에 해당하는 2개의 문자열 P와 Q가 각 줄에 주어집니다.

사전에 있는 문자열들과 질문으로 들어오는 문자열들 P와 Q는 모두 각각 길이가 10만 이하입니다. 사전에 있는 문자열들의 길이 합, P들의 합, Q들의 합 모두 200만 이하입니다.

M개의 줄에 걸쳐 각 질문에 대한 답을 출력합니다.