問題文

JOI 国は N 個の島からなる国であり，各島には 1 から N までの番号が付けられている．現在，この国には島と島の間を結ぶ橋が存在しておらず，住民は不便な生活を送っている．

そこで，JOI 国の大臣であるあなたは国家事業として新たに橋を架けることにした．橋を架ける建設計画が M 個あり，j 番目 (1 \leqq j \leqq M) の建設計画は，費用 C_j をかけて，島 A_j と島 B_j の間を双方向に結ぶ橋を架けるものである．ここで，C_1, C_2, \ldots, C_M は相異なることが保証される．また，すべての建設計画を実行した場合において，すべての島がいくつかの橋によって互いに到達可能になることが保証される．

JOI 国の予算は限られているので，あなたは，次のように国家事業を実施することに決めた．

1. N 個の島の中からひとつの島 s を選び，その島を首都とする．
2. 以下の操作を N - 1 回行う．
   • 各操作をする前の時点で，いくつかの橋を用いて首都から到達可能である島を近い島，そうでない島を遠い島とする． 架ける橋の一端が近い島，もう一端が遠い島であるような建設計画のうち，費用が最も安いものを選び，実行する．
3. 操作を N - 1 回行った後，国家事業を終了する．

ここで，建設計画の満たす制約より，以下の事柄を証明できる．

• 各操作において，選ぶことのできる建設計画は必ず存在する．さらに，実行される建設計画は一意に定まる．
• この事業が終了した時点で，すべての島がいくつかの橋によって互いに到達可能になる．

JOI 国への移住を検討している凛は，どの島に住むかの参考にするため，次のように各島の不便度を計算することにした． 島 i (1 \leqq i \leqq N) の不便度は次のように定義される．

• 島 s (1 \leqq s \leqq N) を首都として国家事業を実施したときに，島 i が首都から到達可能になるまでに実行された建設計画の数を D_{s, i} とする．ここで，s = i のときは D_{s, i} は 0 とする．
• 島 i の不便度は，すべての 1 \leqq s \leqq N に対する D_{s, i} の総和とする．

凛は，引っ越し先の候補としている Q 個の島 X_1, X_2, \ldots, X_Q の不便度を計算したい．建設計画と引っ越し先の候補の島の情報が与えられたとき，これらの島の不便度を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 300\,000．
• 1 \leqq M \leqq 600\,000．
• 1 \leqq Q \leqq N．
• 1 \leqq A_j < B_j \leqq N (1 \leqq j \leqq M)．
• すべての建設計画を実行した場合において，すべての島がいくつかの橋によって互いに到達可能になる．
• 1 \leqq C_j \leqq 10^9 (1 \leqq j \leqq M)．
• C_1, C_2,\ldots,C_M は相異なる．
• 1 \leqq X_k\leqq N (1 \leqq k \leqq Q)．
• X_1, X_2, \ldots, X_Q は相異なる．
• 入力される値はすべて整数である．

小課題

1. (5 点) N \leqq 2\,000，M \leqq 2\,000．
2. (8 点) N \leqq 2\,000．
3. (9 点) M = N - 1，A_j = j, B_j = j + 1 (1 \leqq j \leqq M)，Q = 1．
4. (18 点) M = N - 1，A_j = j, B_j = j + 1 (1 \leqq j \leqq M)．
5. (28 点) Q = 1．
6. (32 点) 追加の制約はない．

入力例 1

4 5 2
1 3 2
1 4 4
2 3 1
2 4 5
3 4 3
1
3

出力例 1

7
3

例えば，島 1 を首都として，国家事業を実施した場合を考える．このとき，次のように建設計画が実行される．

1. 1 番目の建設計画が実行される．首都からは新たに島 3 が到達可能になる．
2. 3 番目の建設計画が実行される．首都からは新たに島 2 が到達可能になる．
3. 5 番目の建設計画が実行される．首都からは新たに島 4 が到達可能になる．

以上より，D_{1, 1} = 0, D_{1, 2} = 2, D_{1, 3} = 1, D_{1, 4} = 3 となる．

D_{2, 1} = 2, D_{3, 1} = 2, D_{4, 1} = 3 であるため，島 1 の不便度は D_{1, 1} + D_{2, 1} + D_{3, 1} + D_{4, 1} = 0 + 2 + 2 + 3 = 7 である．また，D_{2, 3} = 1, D_{3, 3} = 0, D_{4, 3} = 1 であるため，島 3 の不便度は D_{1, 3} + D_{2, 3} + D_{3, 3} + D_{4, 3} = 1 + 1 + 0 + 1 = 3 である．

この入力例は小課題 1, 2, 6 の制約を満たす．

入力例 2

5 4 5
1 2 3
2 3 1
3 4 4
4 5 2
1
2
3
4
5

出力例 2

12
8
7
10
13

この入力例は小課題 1, 2, 4, 6 の制約を満たす．

入力例 3

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

出力例 3

43

この入力例は小課題 1, 2, 5, 6 の制約を満たす．