配点 : $600$ 点

問題文

$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$ 階に移動することが可能か判定し、可能な場合は移動時間の最小値を求めてください。

制約

• $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