Fragments

You are given a set $A$ of positive integers, described as a union of closed intervals. For a string of digits $x$, determine how many times $x$ occurs as a fragment (a contiguous substring) inside the decimal representations of the numbers in $A$. If $x$ occurs several times inside one number, every occurrence is counted, and occurrences are allowed to overlap.

The first line contains two integers $n$ and $m$ ($1 \le n \le 5000$, $1 \le m \le 500000$): the number of intervals describing the set $A$ and the number of queries.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$. They satisfy $1 \le a_1 \le b_1 < a_2 \le b_2 < a_3 \le b_3 < \dots < a_n \le b_n \le 10^{18}$ and describe the set $A = [a_1, b_1] \cup [a_2, b_2] \cup \dots \cup [a_n, b_n]$, where each interval is inclusive on both ends.

Each of the next $m$ lines contains one query: a string of digits $x_j$ with between $1$ and $19$ digits, each digit from $0$ to $9$. A query string may start with the digit $0$.

Print $m$ lines. The $j$-th line must contain a single integer: the total number of occurrences of $x_j$ as a fragment across all numbers in the set $A$, counting every occurrence separately, including repeated and overlapping occurrences inside the same number.