/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
ある冷蔵庫では、ドリンクに 6 桁の数字列を ID として割り振っています。
この冷蔵庫には N 個のドリンクが保管されています。 i 番目のドリンクの ID は S_i、サイズは V_i です。 S_1, \dots, S_N は相異なります。
Q 個のクエリに答えてください。各クエリは 6 桁の数字列 x, y の形式で与えられ、内容は以下の通りです。
- この冷蔵庫にあるドリンクのうち、割り振られた ID s がどの k = 1, \dots, 6 についても以下を満たすようなものについて、そのサイズの総和を求めよ。
- s, x, y の k 桁目の数字が表す値を s_k, x_k, y_k とおいたとき、x_k \leq s_k \leq y_k を満たす。
制約
- N は整数
- 1 \leq N \leq 3 \times 10^5
- S_i は数字 (
0-9) からなる文字列 - |S_i| = 6
- S_1, \dots, S_N は相異なる
- V_i は整数
- 1 \leq V_i \leq 10^9
- Q は整数
- 1 \leq Q \leq 3 \times 10^5
- 各クエリにおいて、x, y は数字 (
0-9) からなる文字列 - 各クエリにおいて、|x| = |y| = 6
入力
入力は以下の形式で標準入力から与えられる。
N
S_1 V_1
\dots
S_N V_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
ここで、\mathrm{query}_q は q 個目のクエリであり、以下の形式で与えられる。
x y
出力
Q 行出力せよ。q 行目には q 個目のクエリに対する答えを出力せよ。
入力例 1
5 000000 1 314159 2 161803 10 169231 5 384400 20 4 150001 269944 302010 396939 000000 999999 999000 000444
出力例 1
15 0 38 0
1 個目のクエリにおいて、条件を満たすドリンクは 3,4 番目のドリンクです。
2 個目のクエリにおいて、条件を満たすドリンクは存在しません。
3 個目のクエリにおいて、条件を満たすドリンクは 1,2,3,4,5 番目のドリンクです。
4 個目のクエリにおいて、条件を満たすドリンクは存在しません。
入力例 2
8 778722 12744734 488742 359266786 955942 335004463 454854 331175626 934246 179761526 927777 657312747 652568 109900930 753279 405123850 8 201000 785589 202325 955898 310401 875947 044023 988999 111230 567897 133241 577989 101033 999499 453013 796988
出力例 2
515024780 109900930 0 331175626 331175626 331175626 584885376 331175626
Score : 525 points
Problem Statement
A certain refrigerator assigns each drink a 6-digit numeric string as its ID.
This refrigerator stores N drinks. The i-th drink has ID S_i and size V_i. S_1, \dots, S_N are distinct.
Answer Q queries. Each query is given in the form of 6-digit numeric strings x, y, and asks the following.
- Among the drinks stored in this refrigerator, find the sum of the sizes of those whose assigned ID s satisfies the following for every k = 1, \dots, 6.
- x_k \leq s_k \leq y_k, where s_k, x_k, y_k denote the values represented by the k-th digits of s, x, y, respectively.
Constraints
- N is an integer.
- 1 \leq N \leq 3 \times 10^5
- S_i is a string consisting of digits (
0-9). - |S_i| = 6
- S_1, \dots, S_N are distinct.
- V_i is an integer.
- 1 \leq V_i \leq 10^9
- Q is an integer.
- 1 \leq Q \leq 3 \times 10^5
- In each query, x and y are strings consisting of digits (
0-9). - In each query, |x| = |y| = 6.
Input
The input is given from Standard Input in the following format:
N
S_1 V_1
\dots
S_N V_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
Here, \mathrm{query}_q is the q-th query, given in the following format:
x y
Output
Output Q lines. The q-th line should contain the answer to the q-th query.
Sample Input 1
5 000000 1 314159 2 161803 10 169231 5 384400 20 4 150001 269944 302010 396939 000000 999999 999000 000444
Sample Output 1
15 0 38 0
For the first query, the drinks satisfying the condition are the third and fourth drinks.
For the second query, no drinks satisfy the condition.
For the third query, the drinks satisfying the condition are the first, second, third, fourth, and fifth drinks.
For the fourth query, no drinks satisfy the condition.
Sample Input 2
8 778722 12744734 488742 359266786 955942 335004463 454854 331175626 934246 179761526 927777 657312747 652568 109900930 753279 405123850 8 201000 785589 202325 955898 310401 875947 044023 988999 111230 567897 133241 577989 101033 999499 453013 796988
Sample Output 2
515024780 109900930 0 331175626 331175626 331175626 584885376 331175626