Summary

The pass destination for each player is actually determined in at most one way.
Therefore, we can view the players as a graph where the out-degree of each vertex is at most \(1\), and quickly precompute whether the ball will be caught and who the final holder will be for each starting position.

Observation

First, let’s consider the recipient of the pass from player \(i\).

Since player \(i\) passes to the player with the smallest index other than themselves within the pass range \([L_i, R_i]\):

• If \(L_i < i\), the pass destination is \(L_i\).
• If \(L_i = i\) and \(R_i > i\), the pass destination is \(i+1\).
• If \(L_i = R_i = i\), there is no pass destination.

Therefore, the pass destination of each player is uniquely determined.
Let this be nxt[i]. If there is no pass destination, we set nxt[i] = 0.

---

If we naively simulate the passes for each ball, since the ball speed \(W_j\) can be up to \(10^9\), nearly \(10^9\) passes can occur in the worst case.
Since \(M\) is also up to \(2 \times 10^5\), this will not run in time.

---

Thus, we precompute the following information for each player \(i\):

• holder[i]
  The final holder of the ball if it starts from player \(i\) with a sufficiently fast speed.
  However, if the ball is guaranteed to be caught somewhere, this is \(0\).

• C[i]
  The threshold speed such that if the ball starts from player \(i\) with speed \(W\), it will be caught if \(W \leq C[i]\).

For example, suppose the pass destination of player \(i\) is \(u\).

If player \(i\) receives a ball with speed \(W\):

• If \(W \leq D_i\), the ball is caught immediately.
• If \(W > D_i\), the ball is passed to \(u\) with speed \(W-1\).

At player \(u\), the ball is caught if its speed is \(C[u]\) or less.
In other words, from player \(i\)’s perspective, the condition for the ball to be caught after the pass is:

\(W - 1 \leq C[u]\)

which is equivalent to:

\(W \leq C[u] + 1\)

Therefore, the condition for the ball to be caught when starting from player \(i\) is:

\(W \leq \max(D_i, C[u] + 1)\)

Thus, we can compute:

\(C[i] = \max(D_i, C[u] + 1)\)

---

However, the graph may contain cycles.

If the ball enters a cycle, it may visit the same player multiple times.
However, since the speed decreases by \(1\) with each pass and all \(D_i \geq 0\), the speed will eventually become \(0\) or less, and the ball will definitely be caught by someone.

In other words, if a ball starts from a player who reaches a cycle, there is no final holder, and the answer is always \(-1\).

Algorithm

First, find the pass destination nxt[i] for each player.

if L_i < i:
    nxt[i] = L_i
else if R_i > i:
    nxt[i] = i + 1
else:
    nxt[i] = 0

This forms a functional graph where the players are vertices and the passes are edges.

---

Next, we process each vertex in a DFS-like manner.

We prepare a state array state[i]:

• 0: Unvisited
• 1: Currently visiting
• 2: Fully processed

From each unvisited vertex, we follow nxt.

If a cycle is detected

If we reach a vertex that is currently being visited, that part forms a cycle.

Since all vertices on the cycle will eventually catch the ball, we set:

holder[i] = 0
C[i] = INF

Here, INF is a sufficiently large value.

Processing non-cycle parts

For a vertex with no pass destination, i.e., nxt[i] = 0:

• If \(W \leq D_i\), the ball is caught.
• If \(W > D_i\), this player is the final holder.

Therefore:

holder[i] = i
C[i] = D_i

If the pass destination u = nxt[i] is already processed, we can compute it as follows:

If the final holder does not exist from the pass destination

If holder[u] = 0, the ball is guaranteed to be caught at or after player \(u\).
Therefore, starting from player \(i\), it is also guaranteed to be caught.

holder[i] = 0
C[i] = INF

If the final holder exists from the pass destination

If holder[u] exists, the final holder when starting from player \(i\) is the same.

holder[i] = holder[u]
C[i] = max(D_i, C[u] + 1)

By processing in reverse order (e.g., using post-order DFS), the information of the pass destination will always be computed first.

---

Finally, we answer each query \((T, W)\):

• If holder[T] = 0, the ball is guaranteed to be caught, so the answer is \(-1\).
• Even if not, if \(W \leq C[T]\), the ball is caught, so the answer is \(-1\).
• Otherwise, the final holder is holder[T].

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(N)\)

Each player is searched and processed at most once.
Answering each query takes \(O(1)\) time.

Implementation Points

• It is easier to implement if we treat the case of no pass destination as nxt[i] = 0.

• Use the state array for cycle detection.

• Since \(D_i\) can increase by the number of passes, use long long for C[i].

• Vertices that reach a cycle will always have their balls caught, so they can be collectively treated as having holder[i] = 0.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<long long> D(N + 1), C(N + 1);
    vector<int> nxt(N + 1, 0), holder(N + 1, 0), state(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        int L, R;
        cin >> D[i] >> L >> R;

        if (L < i) {
            nxt[i] = L;
        } else if (R > i) {
            nxt[i] = i + 1;
        } else {
            nxt[i] = 0;
        }
    }

    const long long INF = (1LL << 60);

    for (int s = 1; s <= N; s++) {
        if (state[s] != 0) continue;

        vector<int> path;
        int cur = s;

        while (cur != 0 && state[cur] == 0) {
            state[cur] = 1;
            path.push_back(cur);
            cur = nxt[cur];
        }

        int start = (int)path.size() - 1;

        if (cur != 0 && state[cur] == 1) {
            int pos = (int)path.size() - 1;
            while (path[pos] != cur) pos--;

            for (int i = pos; i < (int)path.size(); i++) {
                int v = path[i];
                holder[v] = 0;
                C[v] = INF;
                state[v] = 2;
            }

            start = pos - 1;
        }

        for (int i = start; i >= 0; i--) {
            int v = path[i];

            if (nxt[v] == 0) {
                holder[v] = v;
                C[v] = D[v];
            } else {
                int u = nxt[v];

                if (holder[u] == 0) {
                    holder[v] = 0;
                    C[v] = INF;
                } else {
                    holder[v] = holder[u];
                    C[v] = max(D[v], C[u] + 1);
                }
            }

            state[v] = 2;
        }
    }

    while (M--) {
        int T;
        long long W;
        cin >> T >> W;

        if (holder[T] == 0 || W <= C[T]) {
            cout << -1 << '\n';
        } else {
            cout << holder[T] << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-high.