题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在一条数轴上的不同位置设置了 $N$ 个跳跃台。第 $i$ 个跳跃台拥有一个固定的位置 $X_i$ 和一个初始跳跃力量 $P_i$。你将把一个机器人放置在这条数轴上的某个位置。

机器人会按照以下规则移动：

• 如果机器人所在的位置没有跳跃台，机器人会向左移动 1 个单位。这个过程消耗 1 单位时间。
• 如果机器人所在的位置有跳跃台，机器人会立即启动该跳跃台，并向右跳跃其力量值的距离。跳跃后，该跳跃台的力量会变为原来的两倍。这个过程消耗 1 单位时间。

例如，假设有 $N=2$ 个跳跃台，设置如下。

跳跃台编号	位置 $X_i$	初始力量 $P_i$
1	2
2	5	3

机器人从初始位置 $S = 3$ 出发，移动 $T=7$ 单位时间的过程如下。

时间($T$)	机器人位置	说明	跳跃台状态
0	3	从初始位置开始。	$P_1 = 2, P_2 = 3$
1	2	因为没有跳跃台，向左移动了 1 个单位。
2	4	启动了位置 2 上的 1 号跳跃台，向右跳跃了 2 个单位。	$P_1 = 4, P_2 = 3$
3		因为没有跳跃台，向左移动了 1 个单位。
4	2
5	6	启动了位置 2 上的 1 号跳跃台，向右跳跃了 4 个单位。	$P_1 = 8, P_2 = 3$
6	5	因为没有跳跃台，向左移动了 1 个单位。
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$ 单位时间后到达的位置。

2
2 2
5 3
7
3 1
3 2
3 3
3 4
3 5
3 6
3 7

2
4
3
2
6
5
8

3
-3 3
2 2
11 6
4
1 6
6 12
11 3
9 4

-1
2
15
5

提示

限制条件

• 所有给定的数都是整数。
• $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 分) 无额外限制条件。