Selling RNA Strands

Jaehyun knows only four letters: 'A', 'G', 'C', and 'U'. Hyunsu made up a problem to keep him busy.

Hyunsu's dictionary holds N strings, and Jaehyun has to answer M questions. Each question consists of two strings P and Q. For a question, count how many of the N strings in the dictionary have P as a prefix and Q as a suffix, and print that number.

The count is taken over the dictionary, so every answer is between 0 and N. Inside one string, the part covered by the prefix P and the part covered by the suffix Q may overlap.

The first line contains the number of strings in the dictionary N and the number of questions M, separated by a space. ($1 \le N, M \le 2 \times 10^6$)

Each of the next N lines contains one string of the dictionary.

Each of the following M lines contains the two strings P and Q of one question, separated by a space.

Every dictionary string and every P and Q consists only of the letters 'A', 'G', 'C', and 'U', and each string has length at most $10^5$. The total length of the dictionary strings, the total length of the P strings, and the total length of the Q strings are each at most $2 \times 10^6$.

Print M lines, the answer to each question in the order the questions are given.