로봇

문제

수직선 위 서로 다른 위치에 $NN$개의 점프대가 설치되어 있다. $ii$번 점프대는 고정된 위치 $X_{i}X\_i$와 초기 점프 파워 $P_{i}P\_i$를 가진다. 당신은 이 수직선 위의 어떤 위치에 로봇을 놓을 것이다.

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

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

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

점프대 번호	위치 $X_{i}X\_i$	초기 파워 $P_{i}P\_i$
$11$	$22$	$22$
$22$	$55$	$33$

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

시간 ($TT$)	로봇 위치	설명	점프대 상태
$00$	$33$	초기 위치에서 시작한다.	$P_1=2P\_1\; =\; 2$, $P_2=3P\_2\; =\; 3$
$11$	$22$	점프대가 없으므로 왼쪽으로 $11$칸 이동했다.	$P_1=2P\_1\; =\; 2$, $P_2=3P\_2\; =\; 3$
$22$	$44$	위치 $22$에 있는 $11$번 점프대를 작동시켜 오른쪽으로 $22$만큼 점프했다.	$P_1=4P\_1\; =\; 4$, $P_2=3P\_2\; =\; 3$
$33$	$33$	점프대가 없으므로 왼쪽으로 $11$칸 이동했다.	$P_1=4P\_1\; =\; 4$, $P_2=3P\_2\; =\; 3$
$44$	$22$	점프대가 없으므로 왼쪽으로 $11$칸 이동했다.	$P_1=4P\_1\; =\; 4$, $P_2=3P\_2\; =\; 3$
$55$	$66$	위치 $22$에 있는 $11$번 점프대를 작동시켜 오른쪽으로 $44$만큼 점프했다.	$P_1=8P\_1\; =\; 8$, $P_2=3P\_2\; =\; 3$
$66$	$55$	점프대가 없으므로 왼쪽으로 $11$칸 이동했다.	$P_1=8P\_1\; =\; 8$, $P_2=3P\_2\; =\; 3$
$77$	$88$	위치 $55$에 있는 $22$번 점프대를 작동시켜 오른쪽으로 $33$만큼 점프했다.	$P_1=8P\_1\; =\; 8$, $P_2=6P\_2\; =\; 6$

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

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

입력

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

다음 $NN$개의 줄에 걸쳐 $NN$개의 정수 쌍이 주어진다. 이 중 $ii$ (1 ≤ i ≤ N)번째 줄에는 $X_{i}X\_i$와 $P_{i}P\_i$가 공백을 사이에 두고 주어진다.

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

다음 $QQ$개의 줄에 걸쳐 $QQ$개의 정수 쌍이 주어진다. 이 중 $jj$ (1 ≤ j ≤ Q)번째 줄에는 $S_{j}S\_j$와 $T_{j}T\_j$가 공백을 사이에 두고 주어진다.

출력

$QQ$개의 줄을 출력한다. 이 중 $jj$ (1 ≤ j ≤ Q)번째 줄에는 로봇이 $S_{j}S\_j$에서 출발하여 정확히 $T_{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