AT_joig2022_f タクシー 2 (Taxis 2)

[problemUrl]: https://atcoder.jp/contests/joig2022-open/tasks/joig2022_f IOI 国には，$ 1 $ から $ N $ までの番号が付けられた $ N $ 個の町と，$ 1 $ から $ M $ までの番号が付けられた $ M $ 本の道がある． それぞれの道は，タクシーでのみ通行可能である．道 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) のタクシーは町 $ A_i $ と町 $ B_i $ を**双方向に**移動でき，そのタクシーの色は，$ C_i\ =\ 1 $ のとき赤色，$ C_i\ =\ 2 $ のとき青色である．タクシーには料金がかかり，乗車すると以下のように所持金が変化する． - 乗車前の所持金を $ a $ 円とする． - タクシーが赤色の場合，乗車後の所持金が $ a\ -\ 1 $ 円になる． - タクシーが青色の場合，乗車後の所持金が「$ a\ \div\ 2 $ を整数に切り捨てた値」円になる． あなたは IOI 国の町 $ 1 $ に住んでおり，以下の $ Q $ 個の質問の答えを知っておきたい．$ j $ 番目 ($ 1\ \leqq\ j\ \leqq\ Q $) の質問は以下の通りである． - 町 $ 1 $ から出発し，**$ 1 $ 円以上の所持金を残した状態で**町 $ T_j $ に到着するために，最初に少なくとも何円の所持金を持っている必要があるか．ただし，答えが $ L $ 円よりも大きい場合は，代わりに `Large` と答えよ． 町とタクシーの情報，そして質問の内容が与えられたとき，すべての質問に答えるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ Q $ $ L $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ T_1 $ $ T_2 $ $ \vdots $ $ T_Q $

標準出力に $ Q $ 行で出力せよ．$ j $ 行目 ($ 1\ \leqq\ j\ \leqq\ Q $) には，$ j $ 番目の質問の答えを出力せよ．

### 制約 - $ 2\ \leqq\ N\ \leqq\ 200\,000 $． - $ N\ -\ 1\ \leqq\ M\ \leqq\ 200\,000 $． - $ 1\ \leqq\ Q\ \leqq\ 200\,000 $． - $ 1\ \leqq\ L\ \leqq\ 1\,000\,000\,000 $． - $ 1\ \leqq\ A_i\ \lt\ B_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ (A_i,\ B_i)\ \neq\ (A_j,\ B_j) $ ($ 1\ \leqq\ i\ \lt\ j\ \leqq\ M $)． - $ 1\ \leqq\ C_i\ \leqq\ 2 $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 2\ \leqq\ T_j\ \leqq\ N $ ($ 1\ \leqq\ j\ \leqq\ Q $)． - どの町の間も，いくつかの道を通って行き来できる． - 入力される値はすべて整数である． ### 小課題 1. ($ 9 $ 点) $ M\ =\ N\ -\ 1 $，$ (A_i,\ B_i)\ =\ (i,\ i\ +\ 1) $ ($ 1\ \leqq\ i\ \leqq\ M $)，$ Q\ =\ 1 $，$ N\ \leqq\ 100 $，$ L\ \leqq\ 100 $． 2. ($ 19 $ 点) $ M\ =\ N\ -\ 1 $，$ (A_i,\ B_i)\ =\ (i,\ i\ +\ 1) $ ($ 1\ \leqq\ i\ \leqq\ M $)，$ Q\ =\ 1 $． 3. ($ 19 $ 点) $ M\ =\ N\ -\ 1 $，$ (A_i,\ B_i)\ =\ (i,\ i\ +\ 1) $ ($ 1\ \leqq\ i\ \leqq\ M $)． 4. ($ 16 $ 点) $ N\ \leqq\ 50\,000 $，$ M\ \leqq\ 50\,000 $，$ Q\ =\ 1 $，$ C_i\ =\ 1 $ ($ 1\ \leqq\ i\ \leqq\ M $)． 5. ($ 20 $ 点) $ N\ \leqq\ 50\,000 $，$ M\ \leqq\ 50\,000 $，$ Q\ =\ 1 $． 6. ($ 12 $ 点) $ N\ \leqq\ 50\,000 $，$ M\ \leqq\ 50\,000 $，$ Q\ \leqq\ 50\,000 $． 7. ($ 5 $ 点) 追加の制約はない． ### 採点に関する注意 すべての提出はジャッジシステム上で採点される． 提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる． 各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である． この課題の得点は，**この課題に対するすべての提出の得点の最大値**である． 現在の得点は「提出結果」タブの「自分の得点状況」から確認できる． ### Sample Explanation 1 町 $ 1 $ → 町 $ 2 $ → 町 $ 3 $ → 町 $ 4 $ → 町 $ 5 $ の経路で移動するならば，順に青，赤，青，赤のタクシーに乗ることになる．すると，最初に所持金が $ 10 $ 円あった場合，所持金は $ 10 $ 円 → $ 5 $ 円 → $ 4 $ 円 → $ 2 $ 円 → $ 1 $ 円となり，$ 1 $ 円以上を残した状態で町 $ 5 $ に到着できる． 一方，最初の所持金が $ 9 $ 円以下の場合，$ 1 $ 円以上を残した状態で町 $ 5 $ に到着することはできない． この入力例は小課題 $ 1,\ 2,\ 3,\ 5,\ 6,\ 7 $ の制約を満たす． ### Sample Explanation 2 例えば，$ 1 $ 番目の質問について考えよう． 町 $ 1 $ から出発して町 $ 10 $ に移動するとき，町 $ 1 $ → 町 $ 2 $ → … → 町 $ 9 $ → 町 $ 10 $ の経路をたどることになる．しかし，最初に $ L\ (=\ 25) $ 円持っていたとしても，タクシーを使うごとに所持金が $ 25 $ 円 → $ 12 $ 円 → $ 11 $ 円 → $ 10 $ 円 → … と減っていき，$ 1 $ 円以上を残して町 $ 10 $ にたどり着くことはできない．よって，`Large` と出力しなければならない． この入力例は小課題 $ 3,\ 6,\ 7 $ の制約を満たす． ### Sample Explanation 3 町 $ 1 $ → 町 $ 5 $ → 町 $ 3 $ → 町 $ 2 $ の経路で移動するならば，赤いタクシーに $ 3 $ 回乗ることになる．すると，最初に所持金が $ 4 $ 円あった場合，所持金は $ 4 $ 円 → $ 3 $ 円 → $ 2 $ 円 → $ 1 $ 円となり，$ 1 $ 円以上を残した状態で町 $ 2 $ に到着できる． 一方，最初の所持金が $ 3 $ 円以下の場合，$ 1 $ 円以上を残した状態で町 $ 2 $ に到着することはできない． この入力例は小課題 $ 4,\ 5,\ 6,\ 7 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 6,\ 7 $ の制約を満たす．