시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB0000.000%

문제

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

입력

The first line of the standard input contains two integers n and m (1 ≤ n ≤ 5 000, 1 ≤ m ≤ 500 000) representing the number of lines containing a description of the set A and the number of sequences of digits denoting the queries. Each of the following n lines contains two integers ai and bi. These numbers satisfy the following inequalities: 1 ≤ a1b1 < a2b2 < a3b3 < ... < anbn ≤ 1018 and represent the following set: A = [a1,b1] ∪ [a2,b2] ∪ [a3,b3] ∪ ... ∪ [an,bn].

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

출력

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

예제 입력 1

1 3
2220 2223
222
0
07

예제 출력 1

5
1
0