수직선 위 서로 다른 위치에 N개의 점프대가 설치되어 있다.

i번 점프대는 고정된 위치 X_i와 초기 점프 파워 P_i를 가진다.

당신은 이 수직선 위의 어떤 위치에 로봇을 놓을 것이다.

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

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

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

점프대 번호	위치 X_i	초기 파워 P_i
1	2	2
2	5	3

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

시간(T)	로봇 위치	설명	점프대 상태
0	3	초기 위치에서 시작한다.	P_1=2,P_2=3
1	2	점프대가 없으므로 왼쪽으로 1칸 이동했다.	P_1=2,P_2=3
2	4	위치 2에 있는 1번 점프대를 작동시켜 오른쪽으로 2만큼 점프했다.	P_1=4,P_2=3
3	3	점프대가 없으므로 왼쪽으로 1칸 이동했다.	P_1=4,P_2=3
4	2	점프대가 없으므로 왼쪽으로 1칸 이동했다.	P_1=4,P_2=3
5	6	위치 2에 있는 1번 점프대를 작동시켜 오른쪽으로 4만큼 점프했다.	P_1=8,P_2=3
6	5	점프대가 없으므로 왼쪽으로 1칸 이동했다.	P_1=8,P_2=3
7	8	위치 5에 있는 2번 점프대를 작동시켜 오른쪽으로 3만큼 점프했다.	P_1=8,P_2=6

Q개의 정수 쌍 (Sj,Tj)(1≤j≤Q)이 주어진다.

각 쌍에 대해, 로봇이 위치 S_j에서 출발하여 정확히 T_j의 시간이 지난 후 도달하게 되는 위치를 구하는 프로그램을 작성하라.

로봇의 위치는 서로 독립적으로 계산되어야 하며, 항상 점프대의 초기 상태에서 시작한다.

즉, 각 경우마다 로봇은 수직선 위에 단 하나 존재하며, 점프대의 파워는 입력에서 주어진 초깃값으로부터 다시 시작한다.

제약 조건

로봇 timer 2s memory 1024MB