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 a_i and b_i. These numbers satisfy the following inequalities: 1 ≤ a₁ ≤ b₁ < a₂ ≤ b₂ < a₃ ≤ b₃ < ... < a_n ≤ b_n ≤ 10¹⁸ and represent the following set: A = [a₁,b₁] ∪ [a₂,b₂] ∪ [a₃,b₃] ∪ ... ∪ [a_n,b_n].</p>

Each of the following m lines contains a sequence of digits x_j 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 x_j in all numbers from the set A, including multiple occurrences in respective elements of A.

예제 입력

1 3
2220 2223
222
0
07

예제 출력

5
1
0