当前没有测试数据。

G - 电梯

得分：600 分

问题描述

一个建筑群由 $N$ 座 $10^9$ 层楼高的摩天大楼组成。摩天大楼编号为 $1$ 到 $N$，楼层编号为 $1$ 到 $10^9$。

从任意一座摩天大楼的任意楼层，你可以通过空中通桥在一分钟内到达其它摩天大楼的相同楼层。

此外，还有 $M$ 部电梯。第 $i$ 部电梯在摩天大楼 $A_i$ 的 $B_i$ 层和 $C_i$ 层之间运行。通过这部电梯，你可以在 $|x-y|$ 分钟内从摩天大楼 $A_i$ 的第 $x$ 层到达第 $y$ 层，其中 $x,y$ 是满足 $B_i \le x,y \le C_i$ 的任意整数对。

回答以下 $Q$ 个查询：

• 判断是否可能从摩天大楼 $X_i$ 的第 $Y_i$ 层到达摩天大楼 $Z_i$ 的第 $W_i$ 层，并找出到达目的地所需的最短时间。

约束

• $1 \le N,M,Q \le 2 \times 10^5$
• $1 \le A_i \le N$
• $1 \le B_i < C_i \le 10^9$
• $1 \le X_i,Z_i \le N$
• $1 \le Y_i,W_i \le 10^9$
• 输入中的所有值都是整数。

---

输入

输入通过标准输入给出，具体格式如下：

$N$ $M$ $Q$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

每个查询的格式如下：

``` $X_i$ $Y_i$ $Z_i$ $W_i$ ```

输出

输出 $Q$ 行。第 $i$ 行应该包含一个整数。如果对于 $\mathrm{query}_i$，目的地不可达，则输出 -1；否则，输出到达目的地所需的最短时间。

---

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

12
7
-1

对于第 $1$ 个查询，你可以这样在 $12$ 分钟内到达目的地：

• 使用电梯 $1$ 从摩天大楼 $1$ 的第 $3$ 层到达第 $9$ 层，耗时 $6$ 分钟。
• 使用第 $9$ 层的空中通桥从摩天大楼 $1$ 到达摩天大楼 $3$，耗时 $1$ 分钟。
• 使用电梯 $3$ 从摩天大楼 $3$ 的第 $9$ 层到达第 $14$ 层，耗时 $5$ 分钟。

对于第 $3$ 个查询，目的地不可达，所以应该输出 -1。

---

1 1 1
1 1 2
1 1 1 2

1