The country of JOI consists of $N$ islands, numbered from $1$ to $N$. Currently, there are no bridges connecting the islands, and the residents are living an inconvenient life.

Therefore, you, as a minister of the country of JOI, have decided to build new bridges as a national project. There are $M$ construction plans for bridges, and the $j$-th construction plan ($1 \le j \le M$) involves building a bridge connecting island $A_j$ and island $B_j$ in both directions at a cost of $C_j$. Here, it is guaranteed that $C_1, C_2, \dots, C_M$ are distinct. Also, it is guaranteed that if all construction plans are executed, all islands will be mutually reachable via some bridges.

Since the budget of the country of JOI is limited, you have decided to carry out the national project as follows:

1. Choose one island $s$ from the $N$ islands and make it the capital.
2. Perform the following operation $N - 1$ times:
   • At the time before each operation, islands reachable from the capital using some bridges are called "near islands," and other islands are called "far islands." Among the construction plans where one end of the bridge is a near island and the other end is a far island, choose the one with the lowest cost and execute it.
3. After performing the operation $N - 1$ times, the national project is terminated.

Here, from the constraints satisfied by the construction plans, the following can be proven: In each operation, there is always at least one construction plan that can be chosen. Furthermore, the construction plan to be executed is uniquely determined. At the time this project ends, all islands are mutually reachable via some bridges.

Rin, who is considering moving to the country of JOI, has decided to calculate the "inconvenience" of each island to use as a reference for which island to live on. The inconvenience of island $i$ ($1 \le i \le N$) is defined as follows: Let $D_{s,i}$ be the number of construction plans executed until island $i$ becomes reachable from the capital when the national project is carried out with island $s$ ($1 \le s \le N$) as the capital. Here, $D_{s,i} = 0$ when $s = i$. The inconvenience of island $i$ is the sum of $D_{s,i}$ for all $1 \le s \le N$.

Rin wants to calculate the inconvenience of $Q$ candidate islands for moving, $X_1, X_2, \dots, X_Q$. Given the information about the construction plans and the candidate islands, write a program to find the inconvenience of these islands.

Input

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

$N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$ $X_1$ $X_2$ $\vdots$ $X_Q$

Output

Output $Q$ lines. The $k$-th line should contain the inconvenience of island $X_k$ ($1 \le k \le Q$).

Constraints

• $2 \le N \le 300\,000$.
• $1 \le M \le 600\,000$.
• $1 \le Q \le N$.
• $1 \le A_j < B_j \le N$ ($1 \le j \le M$).
• If all construction plans are executed, all islands will be mutually reachable via some bridges.
• $1 \le C_j \le 10^9$ ($1 \le j \le M$).
• $C_1, C_2, \dots, C_M$ are distinct.
• $1 \le X_k \le N$ ($1 \le k \le Q$).
• $X_1, X_2, \dots, X_Q$ are distinct.
• All input values are integers.

Subtasks

1. (5 points) $N \le 2\,000$, $M \le 2\,000$.
2. (8 points) $N \le 2\,000$.
3. (9 points) $M = N - 1$, $A_j = j, B_j = j + 1$ ($1 \le j \le M$), $Q = 1$.
4. (18 points) $M = N - 1$, $A_j = j, B_j = j + 1$ ($1 \le j \le M$).
5. (28 points) $Q = 1$.
6. (32 points) No additional constraints.

Examples

Input 1

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

Output 1

7
3

Note

For example, consider the case where the national project is carried out with island 1 as the capital. In this case, the construction plans are executed as follows: 1. The 1st construction plan is executed. Island 3 becomes newly reachable from the capital. 2. The 3rd construction plan is executed. Island 2 becomes newly reachable from the capital. 3. The 5th construction plan is executed. Island 4 becomes newly reachable from the capital.

From the above, $D_{1,1} = 0, D_{1,2} = 2, D_{1,3} = 1, D_{1,4} = 3$. Since $D_{2,1} = 2, D_{3,1} = 2, D_{4,1} = 3$, the inconvenience of island 1 is $D_{1,1} + D_{2,1} + D_{3,1} + D_{4,1} = 0 + 2 + 2 + 3 = 7$. Also, since $D_{2,3} = 1, D_{3,3} = 0, D_{4,3} = 1$, the inconvenience of island 3 is $D_{1,3} + D_{2,3} + D_{3,3} + D_{4,3} = 1 + 1 + 0 + 1 = 3$.

Input 2

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

Output 2

12
8
7
10
13

Input 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

Output 3

43