分数: 500 点
问题陈述
有 N 城市编号 1 通过 N,和 M 在这些城市之间往返的巴士。的 i第总线 (1 \leq i \leq M) 从市区出发 A_i 时间 S_i+0.5 并到达城市 B_i 时间 T_i+0.5.
高桥将在这些之间旅行 N 城市。当他在城市时 p 时间 t,他将执行以下操作。
- 如果有从市内出发的巴士 p 不早于时间 t,乘坐公交车中最早发车的公交车前往另一个城市。
- 如果没有这样的巴士,什么也不做,留在城市 p.
高桥重复执行上述操作,直到没有巴士可乘坐。保证所有 M 公交车的发车时间不同,因此乘坐的公交车始终是唯一确定的。此外,换乘巴士所需的时间可以忽略不计。
这是您的任务:流程 Q 查询, i-th (1 \leq i \leq Q) 其内容如下。
- 如果高桥开始他的城市旅行 Y_i 时间 X_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第一个查询如下。
- 如果 Takashi 当时在某辆公交车上 Z_i,按顺序打印两个代表公交车出发城市和公交车到达城市的整数,它们之间有一个空格。
- 否则,即如果高桥当时在某个城市 Z_i,打印代表该城市的整数。
样本输入 1
3 2 3 1 2 1 3 2 3 3 5 1 1 5 2 2 3 1 3 2
示例输出 1
2 3 2 3
在第一个查询中,Takahashi 的行程如下。
- 从城市开始 1 时间 1.
- 乘坐从市区出发的巴士 1 时间 1.5 并到达城市 2 时间 3.5.
- 乘坐从市区出发的巴士 2 时间 3.5 并到达城市 3 时间 5.5.
- 由于没有巴士从城市出发 3 时间 5.5 或之后,留在城市 3 (永远)。
时间 5,他将乘坐从 City 出发的巴士 2 并到达城市 3。因此,按照输出部分中的指定,我们应该打印 2 和 3 之间有一个空格。
示例输入 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
示例输出 2
4 6 1 4 1 8 6 1 1 2 2 7 2 1