问题文

给定一个有 $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