Selling RNA Strands

Time limit1.5sMemory limit1536 MB

Summary

Given N RNA strings, answer M queries that count strings matching a prefix P and suffix Q.

Level: Medium7 of 10
Topics: String matching, Hash map, Two pointers, String
Solved: No attempts yet

Problem

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

Recently, the JOI Company faces a serious decline in profitability from 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 a string consisting of the 4 characters 'A', 'G', 'C', 'U'. For its business, the JOI Company prepares N chains of RNA.

The JOI Company accepts orders of RNA chains from customers in the following form:

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

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

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

Input

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 that in the j-th order, the customer chose two strings Pj, Qj.

Output

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 that match the condition of the j-th order.

Constraints

All input data satisfy the following conditions.

1 ≤ N ≤ 100 000.
1 ≤ M ≤ 100 000.
Each string consists of the 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.

Examples3

Example 1
Input
```
2 3
AUGC
AGC
G C
AU C
A C
```
Expected output
```
0
1
2
```
Example 2
Input
```
3 3
AA
AA
AGA
AA AA
AG GA
AG GA
```
Expected output
```
2
1
1
```

Example 3

Input

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

Expected output