Byteotia is a beautiful land, ruled justly by King Bajtazar the $22^{nd}$. It consists of $n$ villages (numbered from $1$ to $n$) connected by a connected network of $n-1$ roads. The king's castle stands at village number $1$.

The king has $k$ sons who will soon come of age. Each such adult prince will need his own castle, so new castles will be built at some of the villages.

The king and his sons will need to communicate on matters concerning, for example, the security of Byteotia. To this end, messengers will be sent daily from every castle to every other castle with messages. Before each journey, the messengers' horses must be fed with an appropriate amount of grain. Specifically, each of them must eat $1$ decagram of grain for every kilometer traveled.

Write a program that determines the daily grain requirement of Byteotia after the construction of each new castle. Note that for two castles to fully communicate with each other, they send two messengers: one starts from the first castle to deliver a message to the second, and the other messenger does the reverse.

Input

The first line of input contains two integers $n$ and $k$ ($1 \le k < n \le 100\,000$), representing the number of villages in Byteotia and the number of princes.

The next $n-1$ lines describe the road network of Byteotia: each of these lines contains three integers $a, b$, and $c$ ($1 \le a, b \le n, 1 \le c \le 1000$), representing a road connecting villages $a$ and $b$ with a length of $c$ kilometers.

The next $k$ lines describe the numbers of the villages where the successive princes build their castles. Each of these lines contains a single integer $d$ ($2 \le d \le n$). At most one castle can be built at each village (i.e., the successive values of $d$ are pairwise distinct).

Output

Your program should output $k$ lines; the $i$-th line should contain a single integer representing the amount of grain (in decagrams) needed by the messengers' horses after the construction of the $i$-th prince's castle.

Examples

Input 1

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

Output 1

8
40
90

Evaluation

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.