电梯

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有一座由 $N$ 栋 $10^9$ 层高的楼组成的建筑群，楼栋编号为 $1,2,\ldots,N$。任意两栋不同楼的相同楼层之间都有连廊，通过一次连廊需要 $1$ 分钟。

建筑群中有 $M$ 部电梯。第 $i$ 部电梯位于第 $A_i$ 栋楼，覆盖从 $B_i$ 层到 $C_i$ 层的所有楼层。对于任意满足 $B_i\le x,y\le C_i$ 的整数 $x,y$，可以使用该电梯在 $|x-y|$ 分钟内从 $x$ 层移动到 $y$ 层。

回答 $Q$ 个询问。每个询问给出 $X_i,Y_i,Z_i,W_i$，求从第 $X_i$ 栋楼的 $Y_i$ 层到第 $Z_i$ 栋楼的 $W_i$ 层所需的最短时间；若无法到达，输出 $-1$。

输入格式

第一行输入三个整数 $N,M,Q$。

接下来 $M$ 行，第 $i$ 行输入 $A_i,B_i,C_i$，描述一部电梯。

接下来 $Q$ 行，第 $i$ 行输入 $X_i,Y_i,Z_i,W_i$，描述一个询问。

输出格式

输出 $Q$ 行，第 $i$ 行输出第 $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

样例输入 2

1 1 1
1 1 2
1 1 1 2

样例输出 2

1

数据范围

• $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$
• 输入中的所有数均为整数。