問題文

$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 を、そうでないならば移動時間の最小値を出力せよ。

入力例 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$ を使い、ビル $1$ の $3$ 階から $9$ 階へ移動する。この移動には $6$ 分かかる。
• $9$ 階の連絡通路を使い、ビル $1$ からビル $3$ へ移動する。この移動には $1$ 分かかる。
• エレベーター $3$ を使い、ビル $3$ の $9$ 階から $14$ 階で移動する。この移動には $5$ 分かかる。

また、$3$ 番目のクエリについては、移動することが不可能であるため -1 を出力します。

入力例 2

1 1 1
1 1 2
1 1 1 2

出力例 2

1