숫자열 조각 세기

시간 제한1초메모리 제한128 MB

요약

10^18 이하의 서로 겹치지 않는 정수 구간들의 합집합에 속한 모든 수의 십진 표현에서 각 숫자열이 연속 부분 문자열로 몇 번 나타나는지 센다.

난이도: 어려움10점 중 9점
유형: 문자열 매칭, 동적 계획법, 수학, 구현
정답자: 아직 제출이 없습니다

문제

양의 정수들의 집합 $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$ 가 조각으로 나타나는 총 횟수이다. 한 수 안에서 반복되거나 겹쳐서 나타나는 경우도 각각 따로 센다.

예제3

예제 1
입력
```
1 3
2220 2223
222
0
07
```
예상 출력
```
5
1
0
```
예제 2
입력
```
1 1
1 10
1
```
예상 출력
```
2
```
예제 3
입력
```
2 2
1 5
100 105
0
1
```
예상 출력
```
7
8
```