F - 贪婪的 Takahashi

得分：$500$ 分

问题描述

有 $N$ 个编号为 $1$ 到 $N$ 的城市和 $M$ 辆在这些城市之间运行的公交车。第 $i$ 辆公交车 $(1 \leq i \leq M)$ 在时间 $S_i+0.5$ 从城市 $A_i$ 出发，到达城市 $B_i$ 的时间为 $T_i+0.5$。

Takahashi 在这 $N$ 个城市之间旅行。当他在时间 $t$ 在城市 $p$ 时，他会执行以下操作：

1. 如果有辆公交车从城市 $p$ 在时间不早于 $t$ 出发，他会选择最早出发的那辆公交车前往其他城市。
2. 如果没有这样的公交车，他会保持在城市 $p$。

Takahashi 会一直重复以上操作，直到没有可乘坐的公交车。保证所有 $M$ 辆公交车的出发时间不同，所以可乘坐的公交车始终是唯一确定的。此外，换乘所需的时间可以忽略不计。

你的任务是处理 $Q$ 个查询，第 $i$ 个查询 $(1 \leq i \leq Q)$ 如下所示。

• 如果 Takahashi 在时间 $X_i$ 从城市 $Y_i$ 开始旅行，在时间 $Z_i$ 他会在哪个城市或乘坐哪辆公交车上？

约束

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)$
• $A_i \neq B_i\ (1 \leq i \leq M)$
• $1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)$
• $S_i \neq S_j\ (i \neq j)$
• $1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)$
• $1 \leq Y_i \leq N\ (1 \leq i \leq Q)$
• 所有输入都是整数。

输入

输入从标准输入中给出，格式如下：

$N$ $M$ $Q$

$A_1$ $B_1$ $S_1$ $T_1$

$A_2$ $B_2$ $S_2$ $T_2$

$\hspace{1.8cm}\vdots$

$A_M$ $B_M$ $S_M$ $T_M$

$X_1$ $Y_1$ $Z_1$

$X_2$ $Y_2$ $Z_2$

$\hspace{1.2cm}\vdots$

$X_Q$ $Y_Q$ $Z_Q$

输出

输出 $Q$ 行。第 $i$ 行应如下所示为第 $i$ 个查询的回答。

• 如果 Takahashi 在时间 $Z_i$ 所乘坐的交通工具是一辆公交车，则输出两个整数，表示该公交车的出发城市和到达城市，中间用一个空格隔开。
• 否则，即如果 Takahashi 在时间 $Z_i$ 在某个城市里，输出表示该城市的整数。

3 2 3
1 2 1 3
2 3 3 5
1 1 5
2 2 3
1 3 2

2 3
2
3

在第一个查询中，Takahashi 的旅行路线如下所示。

1. 开始于时间为 $1$ 的城市 $1$。
2. 乘坐从城市 $1$ 在时间 $1.5$ 出发、时间 $3.5$ 到达的公交车。
3. 乘坐从城市 $2$ 在时间 $3.5$ 出发、时间 $5.5$ 到达的公交车。
4. 由于没有从城市 $3$ 在时间 $5.5$ 或之后出发的公交车，Takahashi 停留在城市 $3$（永远）。

在时间 $5$，他在乘坐从城市 $2$ 出发、到达城市 $3$ 的公交车上。因此，如输出部分所指定的，我们应该输出 $2$ 和 $3$，中间用一个空格隔开。

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

4
6 1
4 1
8
6 1
1
2
2
7 2
1