Bobland consists of $N$ intersections connected by $N-1$ roads. There are also $K$ shops in the city with the $i$-th shop being located at intersection $a_i$. The location of all shops are distinct. Bob knows that customer $i$ lives at intersection $i$. Customer $i$'s favourite shop is located at intersection $f_i$ and they have a patience value of $p_i$.

We define the distance between two intersections $x$ and $y$ to be the number of roads traversed in the unique shortest path from $x$ to $y$. Bob knows that all customers behave in the following manner: suppose the closest shop to intersection $i$ is distance $d$ away from it. If the distance from customer $i$ to $f_i$ is no more than $d+p_i$, customer $i$ will always prefer to travel further and visit $f_i$ instead. Otherwise, they will visit the closest shop. If multiple shops tie for the closest one, customer $i$ will pick any one of them.

Now Bob is thinking of starting his own shop, but he needs to choose where it will be located. Luckily, Bob is so famous that if his shop ties for shortest distance to a certain customer and that customer's favourite shop is too far away, they will always visit Bob's shop. Having extreme governmental authority, Bob can also set up shop in any intersection, including ones that already have a shop. To help him determine where to set up shop, Bob asks you to determine for each intersection $x$, how many customers will visit his shop if it is located at $x$.

Constraints

Note: for this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you do not need to pass previous subtasks to earn points for later subtasks.

In all subtasks,
$1\le K\le N\le 300000$
$1\le f_i,a_i\le N$
$0\le p_i\le N-1$

Subtask 1 [5%]

$1\le N\le 2000$

Subtask 2 [10%]

The degree of any node is at most $2$.

Subtask 3 [10%]

$K=1$
$p_i=0$

Subtask 4 [75%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ and $K$.
The next $N-1$ lines contain two space-separated integers, $x_i$ $y_i$, describing a road connecting intersection $x_i$ and $y_i$.
The next line contains $K$ space-separated integers, $a_1,a_2,\dots ,a_K$, the locations of the shops.
The next $N$ lines contain two space-separated integers, $f_i$ $p_i$, the favourite shop and patience value of the $i$-th person respectively.

Output Specification

Output one line containing $N$ space-separated integers, the $i$-th of which should be the number of customers that will visit Bob's shop if he places it at intersection $i$.

Sample Input 1

4 1
1 2
1 3
2 4
1
1 1
1 0
1 1
1 0

Sample Output 1

0 2 0 1

Explanation for Sample Output 1

If Bob sets up shop in intersection $2$, he will be visited by customer $2$ and $4$. If he sets up shop in intersection $4$, he will be visited by only customer $4$. He will not be visited by any customers if he sets up shop in intersections $1$ or $3$.

Sample Input 2

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

Sample Output 2

1 1 1 1 1 2