贪婪的高桥君

题目描述

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

高桥君将在这些城市之间旅行。当他在时间 $t$ 位于城市 $p$ 时,他将进行以下操作。

• 如果存在不早于时间 $t$ 从城市 $p$ 出发的公交车,则乘坐其中出发最早的公交车前往另一座城市。
• 如果没有这样的公交车,则不行动,留在城市 $p$。

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

你的任务是处理 $Q$ 个查询,第 $i$ 个查询($1\le i\le Q$)如下。

如果高桥君在时间 $X_i$ 从城市 $Y_i$ 开始旅行,那么在时间 $Z_i$ 他会在哪座城市,或者在哪辆公交车上?

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $Q$
$A_1$ $B_1$ $S_1$ $T_1$
$A_2$ $B_2$ $S_2$ $T_2$
$\vdots$
$A_M$ $B_M$ $S_M$ $T_M$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_Q$ $Y_Q$ $Z_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应包含对第 $i$ 个查询的回答,如下所示。

如果时间 $Z_i$ 时高桥君正在某辆公交车上,输出两个整数,依次为该公交车出发的城市和到达的城市,中间用空格分隔。

否则,即时间 $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

在第一个查询中,高桥君将进行如下旅行。

• 在时间 $1$ 从城市 $1$ 出发。
• 乘坐于时间 $1.5$ 从城市 $1$ 出发、于时间 $3.5$ 到达城市 $2$ 的公交车。
• 乘坐于时间 $3.5$ 从城市 $2$ 出发、于时间 $5.5$ 到达城市 $3$ 的公交车。
• 由于在时间 $5.5$ 及之后没有从城市 $3$ 出发的公交车,因此留在城市 $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

数据范围

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