ボールの挙動を考えましょう。
ボールの移動のルールが \([L_i,R_i]\) の形で与えられますが、実際は次の通りです。

• \(L_i=R_i=i\) であるため、その人からボールが受け渡されることはもうない (以降、 終点 と呼びます) 。
• 人 \(i\) がボールをキャッチできない場合、必ず人 \(j\) にボールを渡す ( \(j=L_i\) あるいは \(j=L_i+1\) )。

ボールがキャッチされた場合に誰がキャッチしたかを求める必要はないため、以下の情報が捕捉できればよいことになります。

• 人 \(i\) にボールを渡した時、辿り着きうる終点(一意に定まります)
• 人 \(i\) にボールを渡した時、終点まで辿り着くのに必要な最小のスピード

上記の \(2\) つの情報を終点から順に遡って全ての人について求めることで、予計算を時間計算量 \(O(N)\) 、ボールひとつにつき求解を時間計算量 \(O(1)\) で行えるため、全体で時間計算量 \(O(N+M)\) でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;
using Graph=vector<vector<int>>;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> D(N+1);
  Graph g(N+1);
  queue<int> q;
  vector<pi> mem(N+1,{-1,-1});
  for(int i=1;i<=N;i++){
    int L,R;
    cin >> D[i] >> L >> R;
    if(L!=i || R!=i){
      if(L==i){g[L+1].push_back(i);}
      else{g[L].push_back(i);}
    }
    else{
      q.push(i);
      mem[i]={i,D[i]+1};
    }
  }
  while(!q.empty()){
    auto od=q.front(); q.pop();
    for(auto &nx : g[od]){
      q.push(nx);
      mem[nx]={mem[od].first,max(mem[od].second,D[nx])+1};
    }
  }
  while(M--){
    int T,W;
    cin >> T >> W;
    if(mem[T].first==-1){cout << "-1\n";}
    else if(W>=mem[T].second){cout << mem[T].first << "\n";}
    else{cout << "-1\n";}
  }
  return 0;
}