Running

Small C thinks running is very interesting, so he decided to create a game called "Running". "Running" is a cultivation game that requires players to log in and complete check-in tasks on time every day.

The map of this game can be viewed as a tree containing $n$ nodes and $n-1$ edges, where each edge connects two nodes, and any two nodes are connected by a unique path. The nodes in the tree are numbered from $1$ to $n$ consecutively.

There are $m$ players, where the $i$-th player has a starting point $S_i$ and an ending point $T_i$. When the daily check-in task begins, all players start from their respective starting points at time $0$ seconds, and run along the shortest path to their own ending points at a speed of one edge per second. Once a player reaches their ending point, they have completed the check-in task. (Since the map is a tree, the path for each person is unique.)

Small C wants to know the activity level of the game, so he placed an observer at each node. An observer at node $j$ will choose to observe at the $W_j$-th second. A player can be observed by this observer if and only if this player arrives at node $j$ exactly at the $W_j$-th second. How many players can each observer at node $j$ observe?

Note: We consider that after a player reaches their destination, they finish the game and cannot wait for a period of time before being observed. That is, for a player with destination $j$: if they arrive at the destination before the $W_j$-th second, the observer at node $j$ cannot observe this player; if they arrive at the destination exactly at the $W_j$-th second, the observer at node $j$ can observe this player.

Input

Read from the file running.in.

The first line contains two integers $n$ and $m$. $n$ is the number of nodes in the tree and also the number of observers, and $m$ is the number of players.

The next $n-1$ lines each contain two integers $u$ and $v$, indicating an edge between node $u$ and node $v$.

The next line contains $n$ integers, where the $j$-th integer is $W_j$, representing the time at which the observer at node $j$ appears.

The next $m$ lines each contain two integers $S_i$ and $T_i$, representing the starting and ending points of a player.

For all data, it is guaranteed that $1 \le S_i, T_i \le n$ and $0 \le W_j \le n$.

Output

Output to the file running.out.

Output one line containing $n$ integers, where the $j$-th integer represents how many players the observer at node $j$ can observe.

Examples

Input 1

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

Output 1

2 0 0 1 1 1

Note 1

For node 1, $W_1 = 0$, so only players starting at node 1 will be observed, thus player 1 and player 2 are observed, total 2 people observed. For node 2, no player is at this node at the 2nd second, total 0 people observed. For node 3, no player is at this node at the 5th second, total 0 people observed. For node 4, player 1 is observed, total 1 person observed. For node 5, player 2 is observed, total 1 person observed. For node 6, player 3 is observed, total 1 person observed.

Input 2

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

Output 2

1 2 1 0 1

Subtasks

The data scale and characteristics for each test case are as follows. Hint: The numbers in the data range can help determine which data type is needed.

Implementation Details

If your program needs to use a large amount of stack space (which usually means deep recursion), please carefully read the document running/stack.pdf in the contestant directory to understand the limits on stack space during final evaluation and how to adjust the stack space limit in the current environment.