로봇

수직선 위 서로 다른 위치에 $N$개의 점프대가 설치되어 있다. $i$번 점프대는 고정된 위치 $X_i$와 초기 점프 파워 $P_i$를 가진다. 당신은 이 수직선 위의 어떤 위치에 로봇을 놓을 것이다.

로봇은 다음과 같은 규칙에 따라 움직인다:

• 로봇이 위치한 지점에 점프대가 없을 경우, 로봇은 왼쪽으로 $1$만큼 이동한다. 이 과정에서 $1$의 시간이 소요된다.
• 로봇이 위치한 지점에 점프대가 있을 경우, 로봇은 즉시 점프대를 작동시켜 오른쪽으로 점프대의 파워만큼 이동한다. 점프 후 점프대의 파워는 기존의 두 배로 증가한다. 이 과정에서 $1$의 시간이 소요된다.

예를 들어, $N = 2$개의 점프대가 다음과 같이 설치되어 있다고 하자.

로봇이 초기 위치 $S = 3$에서 출발하여 $T = 7$만큼의 시간 동안 이동하는 과정은 다음과 같다.

$Q$개의 정수 쌍 $(S_j, T_j)$($1 \leq j \leq Q$)이 주어진다. 각 쌍에 대해, 로봇이 위치 $S_j$에서 출발하여 정확히 $T_j$의 시간이 지난 후 도달하게 되는 위치를 구하는 프로그램을 작성하라.

로봇의 위치는 서로 독립적으로 계산되어야 하며, 항상 점프대의 초기 상태에서 시작한다. 즉, 각 경우마다 로봇은 수직선 위에 단 하나 존재하며, 점프대의 파워는 입력에서 주어진 초깃값으로부터 다시 시작한다.

• 주어지는 모든 수는 정수이다.
• $1 \leq N \leq 300\,000$
• $-10^{17} \leq X_1 < X_2 < ... < X_N \leq 10^{17}$
• $1 \leq P_i \leq 10^{17} (1 \leq i \leq N)$
• $1 \leq Q \leq 300\,000$
• $-10^{17} \leq S_j \leq 10^{17}, 1 \leq T_j \leq 10^{17} (1 \leq j \leq Q)$

1. (5점) $N = 1$
2. (11점) $N = 2$
3. (6점) $N, Q \leq 300$, $1 \leq i \leq N$인 모든 $i$에 대하여 $|X_i|, P_i\leq 300$, $1 \leq j \leq Q$인 모든 $j$에 대하여 $|S_j|, T_j \leq 300$
4. (7점) $N, Q \leq 3\,000$, $1 \leq i \leq N$인 모든 $i$에 대하여 $|X_i|, P_i\leq 3\,000$, $1 \leq j \leq Q$인 모든 $j$에 대하여 $|S_j|, T_j \leq 3\,000$
5. (12점) $N, Q \leq 9\,000$
6. (23점) $N \leq 9\,000$
7. (36점) 추가 제약 조건 없음.

첫 번째 줄에 $N$이 주어진다.

다음 $N$개의 줄에 걸쳐 $N$개의 정수 쌍이 주어진다. 이 중 $i$($1 \leq i \leq N$)번째 줄에는 $X_i$와 $P_i$가 공백을 사이에 두고 주어진다.

다음 줄에는 $Q$가 주어진다.

다음 $Q$개의 줄에 걸쳐 $Q$개의 정수 쌍이 주어진다. 이 중 $j$($1 \leq j \leq Q$)번째 줄에는 $S_j$와 $T_j$가 공백을 사이에 두고 주어진다.

$Q$개의 줄을 출력한다. 이 중 $j$($1\leq j \leq Q$)번째 줄에는 로봇이 $S_j$에서 출발하여 정확히 $T_j$의 시간이 지난 후 도달하는 위치를 출력한다.