24425번 - タクシー 2 (Taxis 2) 서브태스크다국어

IOI 国には，1 から N までの番号が付けられた N 個の町と，1 から M までの番号が付けられた M 本の道がある．

それぞれの道は，タクシーでのみ通行可能である．道 i (1 ≦ i ≦ M) のタクシーは町 A_i と町 B_i を双方向に移動でき，そのタクシーの色は，C_i = 1 のとき赤色，C_i = 2 のとき青色である．タクシーには料金がかかり，乗車すると以下のように所持金が変化する．

• 乗車前の所持金を a 円とする．
• タクシーが赤色の場合，乗車後の所持金が a - 1 円になる．
• タクシーが青色の場合，乗車後の所持金が「a ÷ 2 を整数に切り捨てた値」円になる．

あなたは IOI 国の町 1 に住んでおり，以下の Q 個の質問の答えを知っておきたい．j 番目 (1 ≦ j ≦ Q) の質問は以下の通りである．

• 町 1 から出発し，1 円以上の所持金を残した状態で町 T_j に到着するために，最初に少なくとも何円の所持金を持っている必要があるか．ただし，答えが L 円よりも大きい場合は，代わりに Large と答えよ．

町とタクシーの情報，そして質問の内容が与えられたとき，すべての質問に答えるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

N M Q L
A1 B1 C1
A2 B2 C2
:
AM BM CM
T1
T2
:
TQ

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

• 2 ≦ N ≦ 200 000．
• N - 1 ≦ M ≦ 200 000．
• 1 ≦ Q ≦ 200 000．
• 1 ≦ L ≦ 1 000 000 000．
• 1 ≦ A_i ＜ B_i ≦ N (1 ≦ i ≦ M)．
• (A_i, B_i) ≠ (A_j, B_j) (1 ≦ i ＜ j ≦ M)．
• 1 ≦ C_i ≦ 2 (1 ≦ i ≦ M)．
• 2 ≦ T_j ≦ N (1 ≦ j ≦ Q)．
• どの町の間も，いくつかの道を通って行き来できる．
• 入力される値はすべて整数である．