题目描述

有一个由 $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$ 行应包含 $-1$，如果对于 $\\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

示例输出 1

12
7
-1

对于第 $1$ 个查询，你可以按照以下方式在 $12$ 分钟内到达目标。

• 使用电梯 $1$ 从第 $3$ 层到达大厦 $1$ 的第 $9$ 层，需要 $6$ 分钟。
• 在第 $9$ 层使用空中吊桥从大厦 $1$ 到达大厦 $3$，需要 $1$ 分钟。
• 使用电梯 $3$ 从第 $9$ 层到达大厦 $3$ 的第 $14$ 层，需要 $5$ 分钟。

对于第 $3$ 个查询，目标无法到达，所以应该输出 $-1$。

示例输入 2

1 1 1
1 1 2
1 1 1 2

示例输出 2

1