60013 로봇 Platinum III

문제

수직선 위에 N개의 점프대가 설치되어 있다. 각 점프대 i는 위치 X_i와 초기 점프 파워 P_i를 가진다.

로봇의 움직임 규칙:

• 점프대가 없는 지점: 왼쪽으로 1칸 이동 (시간 1 소요)
• 점프대가 있는 지점: 오른쪽으로 파워만큼 점프 후 파워 2배 증가 (시간 1 소요)

Q개의 쿼리가 주어진다. 각 쿼리마다 시작 위치 S_j에서 시간 T_j가 경과한 후의 최종 위치를 구하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 300,000)이 주어진다.

다음 N줄에 X_i, P_i가 주어진다. (-10^17 ≤ X_i ≤ 10^17, 1 ≤ P_i ≤ 10^17)

다음 줄에 Q (1 ≤ Q ≤ 300,000)가 주어진다.

다음 Q줄에 S_j, T_j가 주어진다. (-10^17 ≤ S_j ≤ 10^17, 1 ≤ T_j ≤ 10^17)

출력

Q줄에 각 쿼리의 최종 위치를 출력한다.

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