로봇 timer 2s memory 1024MB

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

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

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

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

• 로봇이 위치한 지점에 점프대가 없을 경우, 로봇은 왼쪽으로 1만큼 이동한다. 이 과정에서 1의 시간이 소요된다.

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

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

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

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

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

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

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

제약 조건

• 주어지는 모든 수는 정수이다.

• 1≤N≤300 000

• −10^{17}≤X_1<X_2<...<X_N≤10^{17}

• 1≤P_i≤10^{17}(1≤i≤N)

• 1≤Q≤300 000

• −10^{17}≤S_j≤10^{17},1≤T_j≤10^{17}(1≤j≤Q)