在数轴上的不同位置安装了 $N$ 个弹跳台。第 $i$ 个弹跳台固定在位置 $X_i$，且初始弹跳力量为 $P_i$。你将把一个机器人放置在数轴上的某个位置。

机器人根据以下规则移动：

• 如果机器人当前所在的位置没有弹跳台，机器人向左移动 $1$。此过程消耗 $1$ 单位时间。
• 如果机器人当前所在的位置有弹跳台，机器人会立即激活该弹跳台，并向右弹跳等同于该弹跳台当前力量的距离。弹跳后，该弹跳台的力量会加倍（变为原来的两倍）。此过程消耗 $1$ 单位时间。

例如，假设安装了 $N = 2$ 个弹跳台，如下所示：

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

给定 $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 < \dots < 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$
• 1. (11 分) $N = 2$
• 1. (6 分) $N, Q \le 300$，对于所有 $1 \le i \le N$ 满足 $|X_i|, P_i \le 300$，对于所有 $1 \le j \le Q$ 满足 $|S_j|, T_j \le 300$
• 1. (7 分) $N, Q \le 3\,000$，对于所有 $1 \le i \le N$ 满足 $|X_i|, P_i \le 3\,000$，对于所有 $1 \le j \le Q$ 满足 $|S_j|, T_j \le 3\,000$
• 1. (12 分) $N, Q \le 9\,000$
• 1. (23 分) $N \le 9\,000$
• 1. (36 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

2
4
3
2
6
5
8

样例输入 2

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

样例输出 2

-1
2
15
5