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

로봇은 다음과 같은 규칙에 따라 움직인다:
- 로봇이 위치한 지점에 점프대가 없을 경우, 로봇은 왼쪽으로 \(1\)만큼 이동한다. 이 과정에서 \(1\)의 시간이 소요된다.
- 로봇이 위치한 지점에 점프대가 있을 경우, 로봇은 즉시 점프대를 작동시켜 오른쪽으로 점프대의 파워만큼 이동한다. 점프 후 점프대의 파워는 기존의 두 배로 증가한다. 이 과정에서 \(1\)의 시간이 소요된다.

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

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

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

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

• 주어지는 모든 수는 정수이다.
• \(1 ≤ N ≤ 300\, 000\)
• \(−10^{17} ≤ X_1 < X_2 < \dots < 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\))

첫 번째 줄에 \(N\)이 주어진다.

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

다음 줄에는 \(Q\)가 주어진다.

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

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 중등부 3번