题目描述
有 m 堆积木,其中第 i 堆积木位于坐标 xi 的位置,有 ci 块。
反复执行如下操作,直至无法操作:
- 如果存在两块积木坐标相同,则找到满足条件的积木中坐标最小的两块,将一块坐标减 1,另一块坐标加 1,
可以证明在有限次操作之后,所有积木的坐标都会不同,此时无法进行操作。
多次询问,每次给定正整数 k,问最后左数第 k 块积木的位置。保证询问的 k 严格递增。
输入格式
从标准输入读入数据。
第一行一个正整数 m。保证 1≤m≤2×106。
接下来 m 行,其中第 i 行两个正整数 xi,ci。保证 1≤xi≤109,1≤ci≤109。保证 xi 按照输入的顺序严格递增,即 xi<xi+1。
接下来一行一个正整数 q,表示询问个数。保证 1≤q≤2×106。
接下来 q 行,每行一个正整数 k,表示一次询问。保证 1≤k≤m∑i=1ci≤109。保证询问的 k 严格递增。
输出格式
输出到标准输出。
输出 q 行,每行一个整数,其中第 i 行表示第 i 个询问的答案。
样例
输入
2
3 3
4 2
2
2
4
输出
2
5
解释
我们用长度为 5 的单调不降数字字符串描述从左往右五块积木的位置,那么操作过程如下所示:
33344→23444→23345→22445→13445→13355→12455→12446→12356
最终第二块积木坐标为 2,第四块积木坐标为 5。