Score : $500$ points

问题描述

设有 $N$ 座城市，编号从 $1$ 到 $N$，以及 $M$ 辆往返于这些城市的公交车。第 $i$ 辆公交车（$1 \leq i \leq M$）在时间 $S_i+0.5$ 从城市 $A_i$ 发车，并在时间 $T_i+0.5$ 到达城市 $B_i$。

高桥将在这 $N$ 座城市间旅行。当他在时间 $t$ 处于城市 $p$ 时，他将执行以下操作：

1. 如果存在不早于时间 $t$ 从城市 $p$ 发车的公交车，则乘坐其中最早发车的公交车前往另一个城市。
2. 如果不存在这样的公交车，则不做任何事，留在城市 $p$。

高桥会重复执行上述操作，直到没有可乘坐的公交车为止。保证所有 $M$ 辆公交车的发车时间各不相同，因此要乘坐的公交车总是唯一确定的。另外，换乘所需的时间可以忽略不计。

你的任务是处理 $Q$ 个查询，其中第 $i$ 个查询（$1 \leq i \leq Q$）如下所示：

• 如果高桥在时间 $X_i$ 从城市 $Y_i$ 开始旅行，在时间 $Z_i$ 他会处于哪座城市或哪辆公交车上？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ cities numbered $1$ through $N$, and $M$ buses that go between these cities. The $i$-th bus $(1 \leq i \leq M)$ departs from City $A_i$ at time $S_i+0.5$ and arrive at City $B_i$ at time $T_i+0.5$.

Takahashi will travel between these $N$ cities. When he is in City $p$ at time $t$, he will do the following.

1. If there is a bus that departs from City $p$ not earlier than time $t$, take the bus that departs the earliest among those buses to get to another city.
2. If there is no such bus, do nothing and stay in City $p$.

Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all $M$ buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.

Here is your task: process $Q$ queries, the $i$-th $(1 \leq i \leq Q)$ of which is as follows.

• If Takahashi begins his travel in City $Y_i$ at time $X_i$, in which city or on which bus will he be at time $Z_i$?

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $i$-th line should contain the response to the $i$-th query as follows.

• If Takashi is on some bus at time $Z_i$, print two integers representing the city from which the bus departs and the city at which the bus arrives, in this order, with a space between them.
• Otherwise, that is, if Takahashi is in some city at time $Z_i$, print an integer representing that city.

Sample Input 1

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

Sample Output 1

2 3
2
3

In the first query, Takahashi will travel as follows.

1. Start in City $1$ at time $1$.
2. Take the bus that departs from City $1$ at time $1.5$ and arrives at City $2$ at time $3.5$.
3. Take the bus that departs from City $2$ at time $3.5$ and arrives at City $3$ at time $5.5$.
4. Since no bus departs from City $3$ at time $5.5$ or later, stay in City $3$ (forever).

At time $5$, he will be on the bus that departs from City $2$ and arrives at City $3$. Thus, as specified in the Output section, we should print $2$ and $3$ with a space between them.

Sample Input 2

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

Sample Output 2

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

update @ 2024/3/10 09:28:12