16780번 - Selling RNA Strands 서브태스크다국어

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 S_i, 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 P_j, Q_j. This means, in the j-th order, the customer chooses two strings P_j, Q_j.

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 ≤ |S_i| ≤ 100 000 (1 ≤ i ≤ N).
• 1 ≤ |P_j| ≤ 100 000 (1 ≤ j ≤ M).
• 1 ≤ |Q_j| ≤ 100 000 (1 ≤ j ≤ M).
• |S₁| + |S₂| + . . . + |S_N| ≤ 2 000 000.
• |P₁| + |P₂| + . . . + |P_M| ≤ 2 000 000.
• |Q₁| + |Q₂| + . . . + |Q_M| ≤ 2 000 000.

• N ≤ 100.
• M ≤ 100.
• |S_i| ≤ 100 (1 ≤ i ≤ N).
• |P_j| ≤ 100 (1 ≤ j ≤ M).
• |Q_j| ≤ 100 (1 ≤ j ≤ M).

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

• |S₁| + |S₂| + . . . + |S_N| ≤ 100 000.
• |P₁| + |P₂| + . . . + |P_M| ≤ 100 000.
• |Q₁| + |Q₂| + . . . + |Q_M| ≤ 100 000.

There are no additional constraints.