P13522 [KOI 2025 #2] 机器人

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在一条数轴上的不同位置设置了 $N$ 个跳跃台。第 $i$ 个跳跃台拥有一个固定的位置 $X_i$ 和一个初始跳跃力量 $P_i$。你将把一个机器人放置在这条数轴上的某个位置。 机器人会按照以下规则移动： * 如果机器人所在的位置没有跳跃台，机器人会向左移动 1 个单位。这个过程消耗 1 单位时间。 * 如果机器人所在的位置有跳跃台，机器人会立即启动该跳跃台，并向右跳跃其力量值的距离。跳跃后，该跳跃台的力量会变为原来的两倍。这个过程消耗 1 单位时间。 例如，假设有 $N=2$ 个跳跃台，设置如下。 | **跳跃台编号** | **位置** $X_i$ | **初始力量** $P_i$ | | :--------: | :---------: | :-----------: | | 1 | 2 | 2 | | 2 | 5 | 3 | 机器人从初始位置 $S = 3$ 出发，移动 $T=7$ 单位时间的过程如下。 | **时间($T$)** | **机器人位置** | **说明** | **跳跃台状态** | | :----------: | :---------: | :----------------------------------------------------------- | :------------------------- | | 0 | 3 | 从初始位置开始。 | $P_1 = 2, P_2 = 3$ | | 1 | 2 | 因为没有跳跃台，向左移动了 1 个单位。 | $P_1 = 2, P_2 = 3$ | | 2 | 4 | 启动了位置 2 上的 1 号跳跃台，向右跳跃了 2 个单位。 | $P_1 = 4, P_2 = 3$ | | 3 | 3 | 因为没有跳跃台，向左移动了 1 个单位。 | $P_1 = 4, P_2 = 3$ | | 4 | 2 | 因为没有跳跃台，向左移动了 1 个单位。 | $P_1 = 4, P_2 = 3$ | | 5 | 6 | 启动了位置 2 上的 1 号跳跃台，向右跳跃了 4 个单位。 | $P_1 = 8, P_2 = 3$ | | 6 | 5 | 因为没有跳跃台，向左移动了 1 个单位。 | $P_1 = 8, P_2 = 3$ | | 7 | 8 | 启动了位置 5 上的 2 号跳跃台，向右跳跃了 3 个单位。 | $P_1 = 8, P_2 = 6$ | 给定 $Q$ 个整数对 $(S_j, T_j)$ ($1 \le j \le Q$)。对于每对整数，你需要编写一个程序，计算出机器人从位置 $S_j$ 出发，经过恰好 $T_j$ 单位时间后到达的位置。 每次查询都是**独立**计算的，并且总是从跳跃台的初始状态开始。也就是说，每次查询时，数轴上只有一个机器人，且所有跳跃台的力量都会重置为输入给定的初始值。

第一行给定 $N$。 接下来 $N$ 行，每行给出一对整数。其中第 $i$ ($1 \le i \le N$) 行给定了 $X_i$ 和 $P_i$，以空格分隔。 接下来的一行给定 $Q$。 接下来 $Q$ 行，每行给出一对整数。其中第 $j$ ($1 \le j \le Q$) 行给定了 $S_j$ 和 $T_j$，以空格分隔。

输出 $Q$ 行。其中第 $j$ ($1 \le j \le Q$) 行输出机器人从 $S_j$ 出发，经过恰好 $T_j$ 单位时间后到达的位置。

### 限制条件 * 所有给定的数都是整数。 * $1 \le N \le 300\,000$ * $-10^{17} \le X_1 < X_2 < ... < X_N \le 10^{17}$ * $1 \le P_i \le 10^{17}$ ($1 \le i \le N$) * $1 \le Q \le 300\,000$ * $-10^{17} \le S_j\le 10^{17},1\le T_j \le 10^{17}$ ($1 \le j \le Q$) ### 子任务 1. (5 分) $N=1$ 2. (11 分) $N=2$ 3. (6 分) 对于所有 $1 \le i \le N$ 和 $1 \le j \le Q$，满足 $|X_i|, P_i \le 300, |S_j|, T_j \le 300$。 4. (7 分) 对于所有 $1 \le i \le N$ 和 $1 \le j \le Q$，满足 $N, Q \le 3\,000, |X_i|, P_i \le 3\,000, |S_j|, T_j \le 3\,000$。 5. (12 分) $N, Q \le 9\,000$ 6. (23 分) $N \le 9\,000$ 7. (36 分) 无额外限制条件。