电梯

题目描述

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

从任意一座摩天楼的任意楼层，可以使用空中走廊在 1 分钟内到达任何其他摩天楼的同一楼层。

另外，有 $M$ 部电梯。第 $i$ 部电梯在摩天楼 $A_i$ 的 $B_i$ 层与 $C_i$ 层之间运行。使用这部电梯，对于所有满足 $B_i \le x,y \le C_i$ 的整数对 $x,y$，可以从摩天楼 $A_i$ 的 $x$ 层到达 $y$ 层，耗时 $|x-y|$ 分钟。

回答以下 $Q$ 个查询。

判断是否可以从摩天楼 $X_i$ 的 $Y_i$ 层到达摩天楼 $Z_i$ 的 $W_i$ 层；如果可能，求到达所需的最短时间。

输入格式

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

N M Q
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_M B_M C_M
query_1
query_2
⋮
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

数据范围

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