Larry the magical panda has recently purchased a ski resort. Being an avid fan of bamboo trees, he ensured that the ski hills resembled a rooted tree. There are $N$ breakpoints, which are given a unique ID from $1$ to $N$ inclusive. The breakpoint with the ID $1$ will always be the root. There are $N-1$ hills, which connect these breakpoints. The $i$-th hill has a difficulty level of $d_i$. There will be $K$ fellow pandas, the $i$-th of which with a skill level of $s_i$, who will start at breakpoint $1$ and begin skiing. The following process is used by them to determine which hill they will go down:

1. If there are no hills connecting to their current breakpoint, they will stop skiing. Note that a panda will never use a hill that they have already used (otherwise, they would be going uphill).
2. The panda will consider all difficulty levels of the hills connecting to their breakpoint, and will go down the hill that minimizes $|s_i-d_i|$. If there is a tie, they will go down the hill with the lower difficulty level. Out of the hills that they consider, there will never be two with equal difficulty.
3. Go back to step 1.

Larry wants you to help him determine how many pandas will visit each breakpoint so he can efficiently determine how to ambush all the skiers.

Constraints

$1\le N,K\le 2\times {10}^5$

$1\le d_i,s_i\le {10}^9$

A panda will never have to choose between two hills of equal difficulty.

Input Specification

The first line contains $2$ integers $N$ and $K$.

The next $N-1$ lines contain $3$ integers, $a_i$, $b_i$, and $d_i$, representing a hill between breakpoint $a_i$ and $b_i$ with a difficulty level of $d_i$.

The next line contains $K$ integers $s_1,s_2,\dots ,s_k$, representing the skill level of the pandas.

Output Specification

Output a single line containing $N$ integers, with the $i$-th integer denoting the number of pandas who will visit the $i$-th breakpoint.

Sample Input 1

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

Sample Output 1

6 5 1 1 4

Sample Input 2

8 6
1 2 3
2 3 3
2 4 4
4 5 1
4 6 3
2 7 6
1 8 4
1 2 3 4 5 6

Sample Output 2

6 3 3 0 0 0 0 3