题目描述

$N$ 棟の $10^9$ 階建てのビルからなる建物があります。ビルには $1$ から $N$ の番号がついています。

任意の異なるビルの同じ階は連絡通路で結ばれているため $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$ $\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 を、そうでないならば移動時間の最小値を出力せよ。

题目大意

有一个由 $n$ 栋大楼组成的建筑群，编号为$1,2, \dots ,n$。

从任意一栋大楼的某一层，可以使用天桥到达任意一栋楼的同一层，耗时只需要 $1$ 分钟。

另外有 $m$ 个电梯，第 $i$ 部电梯在摩天大楼 $a_i$ 的 $b_i$ 层到 $c_i$ 层这一段运行，这中间的任意一层都能到。比如当前在 $x$ 层，要去往 $y$ 层，要求 $b_i \leq x,y \leq c_i$，耗时为 $\lvert x-y \rvert$。

回答 $q$ 个询问：

• 求能否从第 $x_i$ 栋楼的第 $y_i$ 层到达第 $z_i$ 栋楼的第 $w_i$ 层，如果可以，输出最短需要的时间。

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 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\ <\ C_i\ \le\ 10^9$
• $1\ \le\ X_i,Z_i\ \le\ N$
• $1\ \le\ Y_i,W_i\ \le\ 10^9$
• 入力はすべて整数である。

Sample Explanation 1

$1$ 番目のクエリについては、以下のようにすることで $12$ 分で移動が可能です。 - エレベーター $1$ を使い、ビル $1$ の $3$ 階から $9$ 階へ移動する。この移動には $6$ 分かかる。 - $9$ 階の連絡通路を使い、ビル $1$ からビル $3$ へ移動する。この移動には $1$ 分かかる。 - エレベーター $3$ を使い、ビル $3$ の $9$ 階から $14$ 階で移動する。この移動には $5$ 分かかる。 また、$3$ 番目のクエリについては、移動することが不可能であるため -1 を出力します。