<Submit a solution> [0/10]
Task statistics
Number of users: 38
Number of users with 10 points: 14
Average result: 5.6316

Fragments [A]

Memory limit: 64 MB

We are given a set of positive integers. For a given sequence of digits , we would like to know how many times it occurs, as a fragment (i.e., a contiguous part), in the numbers from the set . Note that a sequence may occur as a fragment of a given multiple times - then we are interested in all its occurrences.

Input

The first line of the standard input contains two integers and (, ) representing the number of lines containing a description of the set and the number of sequences of digits denoting the queries. Each of the following lines contains two integers and . These numbers satisfy the following inequalities: and represent the following set:

Each of the following lines contains a sequence of digits consisting of at least 1 and at most 19 digits .

Output

Your program should write lines to the standard output. The -th of these lines should contain a single integer: the total number of occurrences of in all numbers from the set , including multiple occurrences in respective elements of .

Example

For the input data:

1 3
2220 2223
222
0
07

the correct result is:

5
1
0

Task author: Jakub Radoszewski.

<Submit a solution> [0/10]