AT_joi2025ho_c ミ・テレフェリコ (Mi Teleférico)

ボリビアの首都であるラパスは観光地であるとともに，ミ・テレフェリコ(Mi Teleférico)というロープウェイ路線網でも有名である．あなたはラパスに観光に来ており，できるだけ多くの場所を観光したいと思っている．ここで，現実を単純化した次のような状況設定を考えたい． ラパスには $ N $ 個のロープウェイ駅があり，標高が低い順に $ 1 $ から $ N $ までの番号が付けられている．また， $ M $ 個の**一方通行の**路線があり， $ 1 $ から $ M $ までの番号が付けられている．さらに， $ P $ 個のロープウェイ会社があり， $ 1 $ から $ P $ までの番号が付けられている．各路線は $ 1 $ つの会社によって管理されている．路線 $ i $ ( $ 1 \leqq i \leqq M $ ) は駅 $ A_i $ から駅 $ B_i $ に向かって運行しており，会社 $ C_i $ によって管理されている．ここで，路線は必ず標高の低い駅から標高の高い駅に向かって運行している．すなわち， $ A_i < B_i $ が成立している． 利便性のために，ラパスの交通局はフリーパスを発行した．それぞれのフリーパスには $ 1 \leqq l \leqq r \leqq P $ を満たす $ 2 $ つの整数 $ l, r $ が書かれており，会社 $ l, l + 1, \dots, r $ によって管理されている路線に乗ることができる．すなわち， $ 1 \leqq i \leqq M $ を満たす整数 $ i $ について $ l \leqq C_i \leqq r $ を満たすならば路線 $ i $ に乗ることができる．ここで， $ 1 $ つのフリーパスを複数の路線で使うことも可能である．このフリーパスをフリーパス $ (l, r) $ とする． さて，ラパスに $ 1 $ から $ Q $ までの番号が付けられた $ Q $ 人の観光客が訪れた．観光客 $ j $ ( $ 1 \leqq j \leqq Q $ ) はフリーパス $ (L_j, R_j) $ と，現金 $ X_j $ ボリビアーノを持っている． 観光客の目標は，持っているフリーパスを使って乗ることができる路線のみを用いて，駅 $ 1 $ から移動できない駅がないようにすることである．そのために，観光客 $ j $ ( $ 1 \leqq j \leqq Q $ ) は以下の手順で表される交換を行うことができる．ただし，各観光客について，交換は高々 $ 1 $ 回しか行うことができない． 1. $ 1 \leqq l' \leqq r' \leqq P $ を満たす $ 2 $ つの整数 $ l', r' $ を決める． 2. フリーパス $ (L_j, R_j) $ とフリーパス $ (l', r') $ を交換する．手数料として $ |L_j - l'| + |R_j - r'| $ ボリビアーノを要する． あなたの目的は，それぞれの観光客について，持っている現金の範囲内で目標を達成することができるかを判定することである． 路線と観光客の情報が与えられたとき，それぞれの観光客について，持っている現金の範囲内で目標を達成することができるかを判定するプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ P $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ Q $ $ L_1 $ $ R_1 $ $ X_1 $ $ L_2 $ $ R_2 $ $ X_2 $ $ \vdots $ $ L_Q $ $ R_Q $ $ X_Q $

標準出力に $ Q $ 行で出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には，観光客 $ j $ が目標を達成することができる場合は `Yes` を，そうでない場合は `No` を出力せよ． ---

### 小課題 1. ( $ 7 $ 点) $ N \leqq 50 $ ， $ M \leqq 50 $ ， $ Q \leqq 50 $ ， $ X_j = 0 $ ( $ 1 \leqq j \leqq Q $ )． 2. ( $ 8 $ 点) $ P \leqq 10 $ ． 3. ( $ 11 $ 点) $ P \leqq 100 $ ． 4. ( $ 23 $ 点) $ P \leqq 300\,000 $ ， $ X_j = 0 $ ( $ 1 \leqq j \leqq Q $ )． 5. ( $ 9 $ 点) $ P \leqq 300\,000 $ ． 6. ( $ 22 $ 点) $ N \leqq 8\,000 $ ， $ M \leqq 8\,000 $ ． 7. ( $ 20 $ 点) 追加の制約はない． --- ### Sample Explanation 1 まず，観光客 $ 1 $ については，最初フリーパス $ (3, 7) $ と現金 $ 0 $ ボリビアーノを持っている．この観光客は，フリーパスの交換を行わないことで目標を達成できる．なぜなら，フリーパス $ (3, 7) $ により乗ることができる路線は $ 1, 2, 3, 4 $ の $ 4 $ つであり，この $ 4 $ つの路線を用いて，以下のように駅 $ 1 $ から各駅に移動することができるからである． - 路線 $ 3 $ を用いることで，駅 $ 1 \to 2 $ と移動することができる． - 路線 $ 1, 4 $ をこの順に用いることで，駅 $ 1 \to 2 \to 3 $ と移動することができる． - 路線 $ 3, 2 $ をこの順に用いることで，駅 $ 1 \to 2 \to 4 $ と移動することができる． したがって， $ 1 $ 行目に `Yes` を出力する． 次に，観光客 $ 2 $ については，最初フリーパス $ (5, 6) $ と現金 $ 0 $ ボリビアーノを持っているが，この観光客は目標を達成することができない．なぜなら，フリーパス $ (5, 6) $ により乗ることができる路線は路線 $ 3, 4 $ の $ 2 $ つのみであり，この $ 2 $ つの路線を用いて，駅 $ 1 $ から駅 $ 4 $ へ移動することができないからである．また，現金を $ 0 $ ボリビアーノしか持っていないため，異なるフリーパスと交換することができないからである． したがって， $ 2 $ 行目に `No` を出力する． さらに，観光客 $ 3 $ については目標を達成することができず，観光客 $ 4 $ については目標を達成することができるため， $ 3 $ 行目に `No` を出力し， $ 4 $ 行目に `Yes` を出力する． この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 2 路線の情報は入力例 $ 1 $ と同じである． まず，観光客 $ 1 $ については最初フリーパス $ (5, 6) $ と現金 $ 10 $ ボリビアーノを持っている．この観光客は，フリーパスの交換を次のように行うことで目標を達成できる． 1. $ 1 \leqq l' \leqq r' \leqq P $ を満たす $ 2 $ つの整数として $ l' = 1, r' = 5 $ と決める． 2. フリーパス $ (5, 6) $ とフリーパス $ (1, 5) $ を交換する．手数料として $ |5-1|+|6-5|=5 $ ボリビアーノを要する． したがって， $ 1 $ 行目に `Yes` を出力する． 次に，観光客 $ 2 $ については最初フリーパス $ (3, 4) $ と現金 $ 1 $ ボリビアーノを持っている．この観光客はどのようなフリーパスの交換を行っても，目標を達成することができない． したがって， $ 2 $ 行目に `No` を出力する． さらに，観光客 $ 3 $ については目標を達成することができるため， $ 3 $ 行目に `Yes` を出力する． この入力例は小課題 $ 2,3,5,6,7 $ の制約を満たす． --- ### Sample Explanation 3 この路線において，駅 $ 1 $ から駅 $ 3 $ へ移動することができない．したがって，フリーパスによらず，観光客は目標を達成することはできない． この入力例は小課題 $ 6,7 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 5,6,7 $ の制約を満たす． ### Constraints - $ 2 \leqq N \leqq 300\,000 $ ． - $ 1 \leqq M \leqq 300\,000 $ ． - $ 1 \leqq P \leqq 10^9 $ ． - $ 1 \leqq A_i < B_i \leqq N $ ( $ 1 \leqq i \leqq M $ )． - $ 1 \leqq C_i \leqq P $ ( $ 1 \leqq i \leqq M $ )． - $ 1 \leqq Q \leqq 400\,000 $ ． - $ 1 \leqq L_j \leqq R_j \leqq P $ ( $ 1 \leqq j \leqq Q $ )． - $ 0 \leqq X_j \leqq 10^9 $ ( $ 1 \leqq j \leqq Q $ )． - 入力される値はすべて整数である．