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.

Input Format

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 $_{1} ≤ $ b $_{1} < $ a $_{2} ≤ $ b $_{2} < $ a $_{3} ≤ $ b $_{3} < ... < $ a_{n} $ ≤ $ b_{n} $ ≤ 10^{18} and represent the following set: $ A $ = [$ a $_{1},$ b $_{1}] ∪ [$ a $_{2},$ b $_{2}] ∪ [$ a $_{3},$ b $_{3}] ∪ ... ∪ [$ a_{n} $,$ b_{n} $].

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.

Output Format

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 $.

Example

Input

1 3
2220 2223
222
0
07

Output

5
1
0