Overview

By utilizing the property that the pass destination for each player is uniquely determined, we can simulate the movement of each ball efficiently using doubling.

---

Key Observations

1. Uniqueness of Pass Destinations

When player \(i\) passes the ball, the candidate pass destinations are the players in the range \([L_i, R_i]\) excluding player \(i\) themselves, and the player with the “smallest index” is chosen. From the constraint \(L_i \leq i \leq R_i\), the pass destination nxt[i] for each player \(i\) is uniquely determined as follows:

1. When \(L_i < i\): Since there are candidates to the left of player \(i\), the one with the smallest index among them is \(L_i\).
2. When \(L_i = i\) and \(R_i > i\): There are no candidates to the left, and they only exist to the right. Therefore, the candidate with the smallest index is \(i + 1\).
3. When \(L_i = R_i = i\): There are no other players to pass to, so there is no pass destination (player \(i\) becomes the final holder). In this case, for convenience, we set the pass destination to \(0\).

Thus, the pass destination for each player can be found in \(O(1)\) time.

2. Limitations of Naive Simulation

Consider a naive approach where, for each ball, we “simulate the movement step-by-step until it is caught or there are no more pass destinations.” In this case, since the ball’s speed \(W_j\) can be up to \(10^9\) and the number of passes can be up to \(O(N)\), simulating one ball can take \(O(N)\) time in the worst case. Since the number of balls \(M\) is also up to \(2 \times 10^5\), the overall time complexity would be \(O(NM)\), which leads to a Time Limit Exceeded (TLE) verdict.

3. Acceleration via Doubling

The passes between players can be viewed as a “directed graph where the out-degree of each vertex is at most 1 (at most one transition destination).” In such a structure, we can speed up the simulation by applying doubling to precompute the “transitions after \(2^k\) steps.”

However, in this problem, we cannot just move blindly; we must also check the condition “whether the ball gets caught along the way (the speed \(W\) becomes less than or equal to the player’s catching power \(D\)).” Therefore, during the doubling process, we also maintain the “minimum speed required at the starting point to proceed without being caught along the way.”

---

Algorithm

1. Definition of Doubling Tables

Let \(K = 30\) (since \(2^{30} > 10^9\)), and define the following two tables:

• to[k][i]: The player reached after starting from player \(i\) and passing \(2^k\) times (or \(0\) if there are no more pass destinations along the way).
• max_val[k][i]: The minimum ball speed required at the starting point to avoid being caught during the process of passing \(2^k\) times (or until stopping) starting from player \(i\).
  • If the initial speed of the ball is \(W\), and \(W \leq \text{max\_val}[k][i]\), the ball will be caught at some point during these \(2^k\) steps.

2. Table Initialization and Transitions

Base Cases (\(k = 0\), i.e., 1-step movement)

• to[0][i] = nxt[i]
• max_val[0][i] = max(D[i], D[nxt[i]] + 1)
  • The condition for being caught by player \(i\) themselves is \(W \leq D_i\).
  • The condition for being caught by the next player nxt[i] is, based on the speed after the move, \(W - 1 \leq D_{nxt[i]} \iff W \leq D_{nxt[i]} + 1\).
  • Since the ball is caught if either condition is met, we take the maximum of these values.

Transitions (\(k \to k+1\), i.e., \(2^{k+1}\)-step movement)

A movement of \(2^{k+1}\) steps can be decomposed into “moving \(2^k\) steps from \(i\) to reach \(u = \text{to}[k][i]\), and then moving another \(2^k\) steps from there.” * to[k+1][i] = to[k][u] * max_val[k+1][i] = max(max_val[k][i], max_val[k][u] + 2^k) * The condition for being caught in the first \(2^k\) steps is \(W \leq \text{max\_val}[k][i]\). * The condition for being caught in the latter \(2^k\) steps, based on the speed at the start of the second half (when reaching \(u\)), is \(W - 2^k \leq \text{max\_val}[k][u] \iff W \leq \text{max\_val}[k][u] + 2^k\).

3. Query Processing

For each ball \((T, W)\), we simulate the process using the following steps:

1. Check at the Initial Position: If \(W \leq D_T\), the ball is caught without moving even a single step, so we immediately output -1.
2. Jumping via Doubling: Iterate \(k\) from \(29, 28, \ldots, 0\). If the next destination exists (to[k][curr] != 0) and we can move \(2^k\) steps without being caught (W > max_val[k][curr]):
   • We actually move \(2^k\) steps: update curr = to[k][curr] and decrease the speed as W -= 2^k.
3. Final Decision: When we can no longer move forward, if the next pass destination to[0][curr] is \(0\) (no destination), then curr is the final holder. Otherwise, the ball will inevitably be caught in the next step, so the answer is -1.

---

Complexity Analysis

• Time Complexity: \(O((N + M) \log W_{\max})\)
  • Constructing the doubling table takes \(O(N \log W_{\max})\) time.
  • In each query, trying the doubling transitions takes \(O(\log W_{\max})\) time. Since there are \(M\) queries, this takes \(O(M \log W_{\max})\) in total.
  • Since \(W_{\max} \le 10^9\), we have \(\log W_{\max} \approx 30\), which is well within the time limit.
• Space Complexity: \(O(N \log W_{\max})\)
  • Since we store 2D arrays to and max_val of size \(30 \times (N+1)\), the space complexity is \(O(N \log W_{\max})\).

---

Implementation Points

• Using a Sentinel: To uniformly handle cases where there is no pass destination (nxt[i] = 0) or transitions go out of bounds, we treat index 0 as a sentinel. By setting D[0] = -INF, we can prevent bugs such as the ball being caught after passing to a non-existent player.

• Bitwise Operations: Calculating \(2^k\) can be implemented quickly and concisely using 1 << k.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])

    D = [0] * (N + 1)
    L = [0] * (N + 1)
    R = [0] * (N + 1)

    idx = 2
    for i in range(1, N + 1):
        D[i] = int(input_data[idx])
        L[i] = int(input_data[idx + 1])
        R[i] = int(input_data[idx + 2])
        idx += 3

    nxt = [0] * (N + 1)
    for i in range(1, N + 1):
        if L[i] < i:
            nxt[i] = L[i]
        elif L[i] == i and R[i] > i:
            nxt[i] = i + 1
        else:
            nxt[i] = 0

    K = 30
    to = [[0] * (N + 1) for _ in range(K)]
    INF = 10**18
    max_val = [[-INF] * (N + 1) for _ in range(K)]

    D[0] = -INF
    to_0 = to[0]
    max_val_0 = max_val[0]
    for i in range(1, N + 1):
        nxt_i = nxt[i]
        to_0[i] = nxt_i
        val1 = D[i]
        val2 = D[nxt_i] + 1
        max_val_0[i] = val1 if val1 > val2 else val2

    to_0[0] = 0
    max_val_0[0] = -INF

    for k in range(K - 1):
        to_k = to[k]
        max_val_k = max_val[k]
        to_kp1 = to[k + 1]
        max_val_kp1 = max_val[k + 1]
        two_k = 1 << k

        for i in range(N + 1):
            u = to_k[i]
            to_kp1[i] = to_k[u]
            val1 = max_val_k[i]
            val2 = max_val_k[u] + two_k
            max_val_kp1[i] = val1 if val1 > val2 else val2

    out = []
    for _ in range(M):
        T = int(input_data[idx])
        W = int(input_data[idx + 1])
        idx += 2

        if W <= D[T]:
            out.append("-1")
            continue

        curr = T
        for k in range(K - 1, -1, -1):
            nxt_node = to[k][curr]
            if nxt_node != 0 and W > max_val[k][curr]:
                curr = nxt_node
                W -= 1 << k

        if to[0][curr] == 0:
            out.append(str(curr))
        else:
            out.append("-1")

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.