QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB
[+1]

# 9991. 背向而行

统计

题目描述

m 堆积木,其中第 i 堆积木位于坐标 xi 的位置,有 ci 块。

反复执行如下操作,直至无法操作:

  • 如果存在两块积木坐标相同,则找到满足条件的积木中坐标最小的两块,将一块坐标减 1,另一块坐标加 1

可以证明在有限次操作之后,所有积木的坐标都会不同,此时无法进行操作。

多次询问,每次给定正整数 k,问最后左数第 k 块积木的位置。保证询问的 k 严格递增。

输入格式

从标准输入读入数据。

第一行一个正整数 m。保证 1m2×106

接下来 m 行,其中第 i 行两个正整数 xi,ci。保证 1xi1091ci109。保证 xi 按照输入的顺序严格递增,即 xi<xi+1

接下来一行一个正整数 q,表示询问个数。保证 1q2×106

接下来 q 行,每行一个正整数 k,表示一次询问。保证 1kmi=1ci109。保证询问的 k 严格递增。

输出格式

输出到标准输出。

输出 q 行,每行一个整数,其中第 i 行表示第 i 个询问的答案。

样例

输入

2
3 3
4 2
2
2
4

输出

2
5

解释

我们用长度为 5 的单调不降数字字符串描述从左往右五块积木的位置,那么操作过程如下所示:

333442344423345224451344513355124551244612356

最终第二块积木坐标为 2,第四块积木坐标为 5。