Problem Description

Given a simple undirected connected graph with \( N \) vertices and \( M \) edges. The \( i \)-th edge connects vertices \( u_i \) and \( v_i \) with weight \( w_i \). \( w_i \) is either a positive integer constant or a variable \( x \). Process all \( Q \) queries as follows:

• In the \( i \)-th query, a positive integer \( a_i \) is given.
• Determine the weight of the minimum spanning tree when \( x = a_i \).

Input Format

The input is given from the standard input in the following format:

Where \( c_i \) is a character 0 or 1, indicating whether \( w_i \) is a constant or a variable. If \( c_i \) is 0, \( w_i \) is a positive integer constant; if \( c_i \) is 1, \( w_i \) is the character 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 \)

Output Format

Output \( Q \) lines. The \( i \)-th line should contain the answer for the \( i \)-th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5
6
6

Sample Input #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

Sample Output #2

1554451938
2793039057
625183720
3562616013
861577690

Notes/Hints

Constraints

• \( 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 \)
• \( (u_i, v_i) \neq (u_j, v_j) \) and \( (u_i, v_i) \neq (v_j, u_j) \) for \( i \neq j \)
• The given graph is connected.
• When \( w_i \) is a constant, \( 1 \le w_i \le 10^9 \)
• \( 1 \le Q \le 5 \times 10^4 \)
• \( 1 \le a_i \le 10^9 \)
• The input, except for the character x, is all integers.

Sample Explanation 1

In this case:
- When \( x \le 5 \), the weight of the minimum spanning tree is \( x + 1 \).
- When \( x \ge 5 \), the weight of the minimum spanning tree is \( 6 \).

见题面 Input 部分

见题面 Output 部分