5. 背向而行

【题目描述】

有 $m$ 堆积木，其中第 $i$ 堆积木位于坐标 $x_i$ 的位置，有 $c_i$ 块。

反复执行如下操作，直至无法操作：

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

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

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

【输入格式】

第一行一个正整数 $m$。保证 $1\le m \le 2\times 10^6$。

接下来 $m$ 行，其中第 $i$ 行两个正整数 $x_i,c_i$。保证 $1\le x_i \le 10^9$，$1\le c_i \le 10^9$。保证 $x_i$ 按照输入的顺序严格递增，即 $x_i<x_{i+1}$。

接下来一行一个正整数 $q$，表示询问个数。保证 $1\le q\le 2\times 10^6$。

接下来 $q$ 行，每行一个正整数 $k$，表示一次询问。保证 $1\le k \le \sum\limits_{i=1}^{m} c_i \le 10^9$。保证询问的 $k$ 严格递增。

【输出格式】

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

【输入样例】

2
3 3
4 2
2
2
4

【输出样例】

2
5

【样例解释】

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

$33344 \to 23444 \to 23345 \to 22445 \to 13445 \to 13355 \to 12455 \to 12446 \to 12356$

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

【来源】

清华大学学生算法协会 GitLink 仓库