问题描述

有 $N$ 个城市，编号从 $1$ 到 $N$，以及 $M$ 辆巴士在这些城市之间行驶。第 $i$ 辆巴士（$1 \leq i \leq M$）从城市 $A_i$ 在时间 $S_i+0.5$ 开出，到达城市 $B_i$ 在时间 $T_i+0.5$。

高桥要在这 $N$ 个城市之间旅行。当他在时间 $t$ 在城市 $p$ 时，他将执行以下操作。

1. 如果有辆巴士在城市 $p$ 从时间 $t$ 开出或之后，乘坐最早离开的那辆车去另一个城市。
2. 如果没有这样的巴士，什么都不做，留在城市 $p$。

高桥重复这样做，直到没有可以乘坐的巴士。保证所有 $M$ 辆巴士出发的时间都不同，所以可以唯一确定要乘坐的巴士。此外，换乘巴士所需的时间可以忽略不计。

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

• 如果高桥在时间 $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$ 个查询的响应，如下所示。

• 如果高桥在时间 $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

在第一个查询中，高桥将按以下方式旅行。

1. 在时间 $1$ 从城市 $1$ 出发。
2. 乘坐从城市 $1$ 在时间 $1.5$ 开出，到达城市 $2$ 在时间 $3.5$ 的巴士。
3. 乘坐从城市 $2$ 在时间 $3.5$ 开出，到达城市 $3$ 在时间 $5.5$ 的巴士。
4. 由于没有巴士在时间 $5.5$ 或之后从城市 $3$ 开出，所以留在城市 $3$（永远）。

在时间 $5$，他将在从城市 $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