시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 1536 MB 35 7 7 87.500%

문제

Do you know Just Odd Inventions Co., Ltd? The bussiness of this company is doing “just odd inventions.” Here we shall abbreviate its name, and call it the JOI Company.

Recently, the JOI Company is faced with a serious decline in its profitability by doing just odd inventions only. It is planning to start a new business. The plan is to sell liquid containing RNA chains. An RNA chain is considered as a string consisting of 4 characters ‘A’, ‘G’, ‘C’, ‘U’. For its business, the JOI Company prepares N chains of RNA.

The JOI Company will accept an order of RNA chains from customers in the following form:

  • A customer chooses two strings P, Q. Then, among RNA chains prepared by the JOI Company, it sells strings whose first |P| characters are P and last |Q| characters are Q. Here, |P|, |Q| are the length of P, Q, respectively.

How many RNA chains prepared by the JOI Company match the conditions of orders from customers?

Given the information on RNA chains prepared by the JOI Company and orders from customers, write a program which calculates the number of RNA chains prepared by the JOI Company which match the conditions of orders from customers.

입력

Read the following data from the standard input.

  • The first line of input contains two space separated integers N, M. This means the JOI Company prepares N chains of RNA, and there are M orders from customers.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains a string Si, which is the i-th RNA chain prepared by the JOI Company.
  • The j-th line (1 ≤ j ≤ M) of the following M lines contains two space separated strings Pj, Qj. This means, in the j-th order, the customer chooses two strings Pj, Qj.

출력

The output consists of M lines. The j-th line (1 ≤ j ≤ M) contains an integer, the number of RNA chains prepared by the JOI Company which match the condition of the j-th order.

제한

All input data satisfy the following conditions.

  • 1 ≤ N ≤ 100 000.
  • 1 ≤ M ≤ 100 000.
  • Each string consists of 4 characters A, G, C, U.
  • 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.

서브태스크 1 (10점)

  • N ≤ 100.
  • M ≤ 100.
  • |Si| ≤ 100 (1 ≤ i ≤ N).
  • |Pj| ≤ 100 (1 ≤ j ≤ M).
  • |Qj| ≤ 100 (1 ≤ j ≤ M).

서브태스크 2 (25점)

  • N ≤ 5 000.
  • M ≤ 5 000.

서브태스크 3 (25점)

  • |S1| + |S2| + . . . + |SN| ≤ 100 000.
  • |P1| + |P2| + . . . + |PM| ≤ 100 000.
  • |Q1| + |Q2| + . . . + |QM| ≤ 100 000.

서브태스크 4 (40점)

There are no additional constraints.

예제 입력 1

2 3
AUGC
AGC
G C
AU C
A C

예제 출력 1

0
1
2

In this sample input, the JOI Company prepares two RNA chains AUGC, AGC.

  • For the first order, output 0 because there is no RNA chain whose first character is G and last character is C.
  • For the second order, output 1 because there is only one RNA chain AUGC whose first characters are AU and last character is C.
  • For the third order, output 2 because there are two RNA chains AUGC, AGC whose first character is A and last character is C.

예제 입력 2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

예제 출력 2

2
1
1

Note that the same RNA chains and/or the same orders can appear more than once. Also, there can be an overlap between the first characters and the last characters chosen for an order. For example, the RNA chain AGA is considered as a string whose first characters are AG and last characters are GA.

예제 입력 3

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

예제 출력 3

1
0
1
2
3
2
0

채점

  • 예제는 채점하지 않는다.