숫자열 조각 세기

양의 정수들의 집합 $A$가 닫힌 구간들의 합집합으로 주어진다. 숫자로 이루어진 문자열 $x$에 대해, $x$가 집합 $A$에 속한 수들의 십진 표기 안에서 조각(연속된 부분 문자열)으로 몇 번 나타나는지 구하라. 하나의 수 안에서 $x$가 여러 번 나타나면 각 등장을 모두 센다. 등장 위치는 서로 겹칠 수 있다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 5000$, $1 \le m \le 500000$). $n$은 집합 $A$를 이루는 구간의 개수, $m$은 질의의 개수이다.

다음 $n$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어지며, $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}$을 만족한다. 이 값들은 집합 $A = [a_1, b_1] \cup [a_2, b_2] \cup \dots \cup [a_n, b_n]$을 나타내며, 각 구간은 양 끝을 포함한다.

이어지는 $m$개의 줄에는 각각 하나의 질의가 주어진다. 질의는 길이가 $1$ 이상 $19$ 이하인 숫자 문자열 $x_j$이며, 각 자리는 $0$부터 $9$까지의 숫자이다. 질의 문자열은 숫자 $0$으로 시작할 수 있다.

$m$개의 줄을 출력한다. $j$번째 줄에는 정수 하나를 출력하는데, 이는 집합 $A$에 속한 모든 수 안에서 $x_j$가 조각으로 나타나는 총 횟수이다. 한 수 안에서 반복되거나 겹쳐서 나타나는 경우도 각각 따로 센다.