RNA 사슬 판매

Just Odd Inventions 주식회사를 아는가? 이 회사의 사업은 "기묘한 발명"을 하는 것이다. 여기에서는 회사 이름을 줄여 JOI 회사라고 부르자.

최근 JOI 회사는 기묘한 발명만 해 온 탓에 수익성이 크게 떨어졌다. 회사는 새 사업을 시작하려 한다. 그 계획은 RNA 사슬이 들어 있는 액체를 파는 것이다. RNA 사슬은 'A', 'G', 'C', 'U' 4개 문자로 이루어진 문자열로 본다. 사업을 위해 JOI 회사는 N개의 RNA 사슬을 준비한다.

JOI 회사는 다음과 같은 형태로 고객의 RNA 사슬 주문을 받는다.

• 고객은 두 문자열 P, Q를 고른다. 그러면 JOI 회사가 준비한 RNA 사슬 가운데 앞 |P|개 문자가 P이고 뒤 |Q|개 문자가 Q인 문자열을 판다. 여기에서 |P|, |Q|는 각각 P, Q의 길이이다.

JOI 회사가 준비한 RNA 사슬 가운데 고객 주문의 조건에 맞는 것은 몇 개인가?

JOI 회사가 준비한 RNA 사슬 정보와 고객 주문이 주어질 때, 고객 주문의 조건에 맞는 RNA 사슬의 개수를 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에 공백으로 구분된 두 정수 N, M이 주어진다. JOI 회사가 RNA 사슬 N개를 준비하며 고객 주문이 M개라는 뜻이다.
• 이어지는 N개 줄의 i번째 줄 (1 ≤ i ≤ N)에는 문자열 Si가 주어진다. JOI 회사가 준비한 i번째 RNA 사슬이다.
• 이어지는 M개 줄의 j번째 줄 (1 ≤ j ≤ M)에는 공백으로 구분된 두 문자열 Pj, Qj가 주어진다. j번째 주문에서 고객이 두 문자열 Pj, Qj를 골랐다는 뜻이다.

출력은 M개 줄로 이루어진다. j번째 줄 (1 ≤ j ≤ M)에는 j번째 주문의 조건에 맞는 JOI 회사 준비 RNA 사슬의 개수를 나타내는 정수가 들어간다.

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 100 000.
• 1 ≤ M ≤ 100 000.
• 각 문자열은 A, G, C, U 4개 문자로 이루어진다.
• 1 ≤ |Si| ≤ 100 000 (1 ≤ i ≤ N).
• 1 ≤ |Pj| ≤ 100 000 (1 ≤ j ≤ M).
• 1 ≤ |Qj| ≤ 100 000 (1 ≤ j ≤ M).
• |S1| + |S2| + . . . + |SN| ≤ 2 000 000.
• |P1| + |P2| + . . . + |PM| ≤ 2 000 000.
• |Q1| + |Q2| + . . . + |QM| ≤ 2 000 000.