← 返回题目列表

AtCoder · abc465_f

F. 谢尔策?

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

某个冰箱为每种饮料分配了一个 6- 数字字符串作为其 ID。

这台冰箱储存 N 饮料。 的 i-th 饮料有 ID S_i 和尺寸 V_i. S_1, \dots, S_N 是不同的。

答案 Q 查询。每个查询都以以下形式给出 6- 数字字符串 x, y,并询问以下问题。

  • 在此冰箱中存储的饮料中,找到分配了 ID 的饮料的尺寸总和 s 满足以下每个 k = 1, \dots, 6.
    • x_k \leq s_k \leq y_k,其中 s_k, x_k, y_k 表示由 k第 位数字 s, x, y。

约束

  • 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

对于第一个查询,满足条件的饮料是第三和第四饮料。

对于第二个查询,没有饮料满足条件。

对于第三个查询,满足条件的饮料是第一、第二、第三、第四、第五饮料。

对于第四个查询,没有饮料满足条件。


示例输入 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