考虑每条边，因为是静态的，所以可以预处理出 \(f_{i,j}, g_{i,j}\) 表示从第 \(i\) 条边，往后跳 \(2^j\) 条边，跳到边的编号和目前的时间（如果不存在就当作跳到第 \(0\) 条边）。直接倍增处理即可。
询问就是找到从 \(u\) 开始的出边，能跳尽量跳。
注意一些细节。
code
// Problem: F - Greedy Takahashi
// Contest: AtCoder - AtCoder Beginner Contest 212
// URL: https://atcoder.jp/contests/abc212/tasks/abc212_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const int logn = 20;
ll n, m, q, f[maxn][logn], g[maxn][logn];
struct E {
ll v, s, t, id;
E(ll a = 0, ll b = 0, ll c = 0, ll d = 0) : v(a), s(b), t(c), id(d) {}
};
inline bool cmp(E a, E b) {
return a.s < b.s;
}
struct node {
ll u, v, s, t;
node(ll a = 0, ll b = 0, ll c = 0, ll d = 0) : u(a), v(b), s(c), t(d) {}
} a[maxn];
vector<E> G[maxn];
vector<pii> qq[maxn];
void solve() {
scanf("%lld%lld%lld", &n, &m, &q);
for (int i = 1, u, v, s, t; i <= m; ++i) {
scanf("%d%d%d%d", &u, &v, &s, &t);
G[u].pb(v, ++s, t, i);
a[i] = node(u, v, s, t);
}
for (int i = 1; i <= n; ++i) {
sort(G[i].begin(), G[i].end(), cmp);
}
f[0][0] = 0;
g[0][0] = 1e18;
for (int u = 1; u <= n; ++u) {
for (E e : G[u]) {
ll v = e.v, t = e.t;
int l = 0, r = (int)G[v].size() - 1, pos = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (G[v][mid].s > t) {
pos = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (pos == -1) {
f[e.id][0] = 0;
g[e.id][0] = 1e18;
} else {
f[e.id][0] = G[v][pos].id;
g[e.id][0] = G[v][pos].t;
}
}
}
for (int j = 1; j <= 18; ++j) {
for (int i = 0; i <= m; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
g[i][j] = g[f[i][j - 1]][j - 1];
}
}
while (q--) {
ll u, x, y;
scanf("%lld%lld%lld", &x, &u, &y);
int l = 0, r = (int)G[u].size() - 1, pos = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (G[u][mid].s > x) {
pos = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (pos == -1) {
printf("%lld\n", u);
continue;
}
if (y < G[u][pos].s) {
printf("%lld\n", u);
continue;
}
if (y <= G[u][pos].t) {
printf("%lld %lld\n", u, G[u][pos].v);
continue;
}
int d = G[u][pos].id;
for (int i = 18; ~i; --i) {
if (g[d][i] < y) {
d = f[d][i];
}
}
if (!f[d][0]) {
printf("%lld\n", a[d].v);
continue;
}
int k = f[d][0];
if (y < a[k].s) {
printf("%lld\n", a[k].u);
} else if (a[k].s <= y && y <= a[k].t) {
printf("%lld %lld\n", a[k].u, a[k].v);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}