On a vertical number line, there are $N$ jump platforms installed at distinct positions. The $i$-th jump platform has a fixed position $X_i$ and an initial jump power $P_i$.

You will place a robot at some position on this number line.

The robot moves according to the following rules:

• If there is no jump platform at the robot’s current position, the robot moves 1 unit to the left. This action takes 1 unit of time.
• If there is a jump platform at the robot’s current position, the robot immediately activates the platform and jumps to the right by the platform’s current power. After the jump, the power of that jump platform doubles. This action also takes 1 unit of time.

For example, suppose there are $N = 2$ jump platforms installed as follows:

If the robot starts at initial position $S = 3$ and moves for $T = 7$ units of time, the process is as follows:

You are given $Q$ integer pairs $(S_j, T_j)$ $(1 \le j \le Q)$. For each pair, write a program that computes the position the robot reaches exactly after $T_j$ units of time, starting from position $S_j$.

Each robot’s movement must be computed independently, and each case always starts with the initial state of the jump platforms. That is, for each query, there is exactly one robot on the number line, and all jump platform powers are reset to the initial values given in the input.

Constraints

• All given values are integers.
• $1 \le N \le 300,000$
• $-10^{17} \le X_1 < X_2 < \cdots < 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)$

Scoring

1. (5 points) $N = 1$
2. (11 points) $N = 2$
3. (6 points) $N, Q \le 300$, and for all $i$, $|X_i|, P_i \le 300$, and for all $j$, $|S_j|, T_j \le 300$
4. (7 points) $N, Q \le 3,000$, and for all $i$, $|X_i|, P_i \le 3,000$, and for all $j$, $|S_j|, T_j \le 3,000$
5. (12 points) $N, Q \le 9,000$
6. (23 points) $N \le 9,000$
7. (36 points) No additional constraints

Input Format

• The first line contains an integer $N$.
• The next $N$ lines each contain two integers $X_i$ and $P_i$, separated by a space.
• The next line contains an integer $Q$.
• The next $Q$ lines each contain two integers $S_j$ and $T_j$, separated by a space.

Output Format

Output $Q$ lines. On the $j$-th line $(1 \le j \le Q)$, output the position that the robot reaches exactly after $T_j$ units of time, starting from $S_j$.

Example

Example 1

Input

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

Output

2
4
3
2
6
5
8

Example 2

Input

3
-3 3
2 2
1 1
6
4 1
6 1
2 1
1 3
9 4
-1 2

Output

1
6
1
9
5
5