AT_abc254_g [ABC254G] Elevators

[problemUrl]: https://atcoder.jp/contests/abc254/tasks/abc254_g $ 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` を、そうでないならば移動時間の最小値を出力せよ。

### 制約 - $ 1\ \le\ N,M,Q\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ A_i\ \le\ N $ - $ 1\ \le\ B_i\