暴力就是直接跳，显然不可过。
考虑对暴力进行优化，发现整个图是不会改变的，容易想到使用倍增。
显然是对边进行倍增的，令 \(f_{i, j}\) 表示从第 \(i\) 条边开始，跳了 \(2^j\) 条边后，到的是哪一条边，如果不存在，则设为 \(-1\)。
然后就是很显然的倍增了，最后讨论一下即可。
时间复杂度：\(\mathcal{O}((m + Q) \log m)\)
代码：
const int N = 1e5 + 10;
int n, m, Q;
int f[N][20];
set<pii> v[N];
typedef set<pii>::iterator iter;
struct edge {
int u, v, s, t;
} e[N];
int get(int u, int val) {
iter it = v[u].lower_bound(mkp(val, 0));
if (it == v[u].end()) return -1;
return (*it).second;
}
int main() {
ios
for (int i = 0; i < N; i++) for (int j = 0; j < 20; j++) f[i][j] = -1;
cin >> n >> m >> Q;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].s >> e[i].t;
v[e[i].u].insert(make_pair(e[i].s, i));
}
for (int i = 1; i <= m; i++) {
f[i][0] = get(e[i].v, e[i].t);
}
for (int j = 1; j <= 19; j++)
for (int i = 1; i <= m; i++)
if (f[i][j - 1] != -1)
f[i][j] = f[f[i][j - 1]][j - 1];
while (Q--) {
int x, y, z; cin >> x >> y >> z;
int now = get(y, x);
if (now == -1) {
cout << y << "\n";
continue;
}
for (int i = 19; i >= 0; i--)
if (f[now][i] != -1 && e[f[now][i]].s < z)
now = f[now][i];
if (z <= e[now].s) cout << e[now].u << "\n";
else if (e[now].t < z) cout << e[now].v << "\n";
else cout << e[now].u << " " << e[now].v << "\n";
}
return 0;
}