問題文

$N$ 頂点 $M$ 辺の単純無向連結グラフが与えられます。 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいて、重みは $w_i$ です。 $w_i$は正整数の定数、もしくは変数 $x$ です。 以下の $Q$ 個のクエリをすべて処理してください。

• $i$ 番目のクエリでは、正整数 $a_i$ が与えられる。
• $x=a_i$ としたときの最小全域木の重みを求めよ。

制約

• $2 \\le N \\le 5 \\times 10^4$
• $N-1 \\le M \\le min(5 \\times 10^4, N(N-1)/2)$
• $1 \\le u_i,v_i \\le N$
• $u_i \\neq v_i$
• $i \\neq j$ のとき $(u_i,v_i) \\neq (u_j,v_j)$ かつ $(u_i,v_i) \\neq (v_j,u_j)$
• 与えられるグラフは連結である。
• $w_i$ が定数のとき、$1 \\le w_i \\le 10^9$
• $1 \\le Q \\le 5 \\times 10^4$
• $1 \\le a_i \\le 10^9$
• 入力は、文字 x を除けば、すべて整数である。

入力

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

ただし、 $c_i$ は文字 0 または 1 であり、これは $w_i$ が定数か変数かを表している。 $c_i$ が 0 のとき、 $w_i$ は正整数の定数であり、 $c_i$ が 1 のとき、 $w_i$ は文字 x である。

$N$ $M$ $u_1$ $v_1$ $c_1$ $w_1$ $u_2$ $v_2$ $c_2$ $w_2$ $:$ $u_M$ $v_M$ $c_M$ $w_M$ $Q$ $a_1$ $a_2$ $:$ $a_Q$

出力

$Q$ 行出力せよ。 $i$ 行目には、 $i$ 番目のクエリの答えを出力せよ。

入力例 1

3 3
1 2 0 1
2 3 0 5
3 1 1 x
3
4
5
6

出力例 1

5
6
6

このケースでは、

• $x \\le 5$ のとき最小全域木の重みは $x+1$
• $x \\ge 5$ のとき最小全域木の重みは $6$

となります。

入力例 2

9 15
1 3 0 954291757
2 3 1 x
2 4 1 x
1 5 0 138996221
2 5 0 353195922
3 5 1 x
4 5 0 913575467
1 6 0 824284691
1 7 1 x
2 7 1 x
1 8 0 131381221
6 8 0 208032501
7 8 0 973708325
5 9 1 x
6 9 0 298309896
5
215208399
554374432
47628333
810900084
87027328

出力例 2

1554451938
2793039057
625183720
3562616013
861577690

• Rule

• Glossary

• Terms of service

• Privacy Policy

• Information Protection Policy

• Company

• FAQ

• Contact

Copyright Since 2012 ©AtCoder Inc. All rights reserved.