Daily Running Observation

Little C finds running extremely fun and has therefore created a game called Daily Running. In this game, each player must log in daily and complete a check‐in task. The game map is represented by a tree with \(n\) nodes and \(n-1\) edges. Each edge connects two nodes and there is a unique path between any two nodes. The nodes are numbered consecutively from 1 to \(n\).

There are \(m\) players. The \(i\)th player starts from node \(s_i\) and aims to reach node \(t_i\). When the daily check‐in begins at time 0, all players simultaneously start running from their starting nodes. They run continuously along the unique shortest path toward their targets, at a speed of one edge per second. As soon as a player reaches his/her target, the check‐in task for that player is completed and the player immediately leaves the game. (Note that if a player reaches his/her target before the observer’s designated time, he/she cannot be observed later.)

Each node \(j\) has an observer who watches at time \(w_j\) seconds. An observer at node \(j\) will record a player if and only if the player is exactly at node \(j\) at time \(w_j\) seconds. In particular, if node \(j\) is a player’s target, the player will only be observed if he/she arrives exactly at time \(w_j\), and if he/she arrives earlier the observer will not record him/her.

Your task is to determine, for each node, how many players are observed by the observer placed at that node.

Note: A player who reaches his/her target at time \(w_j\) is observed, but if the target is reached before \(w_j\), the player is not observed.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq \text{small constraints})\), representing the number of nodes and the number of players respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), denoting an edge connecting node \(u\) and node \(v\).

The following line contains \(n\) integers \(w_1, w_2, \ldots, w_n\), where \(w_j\) is the time (in seconds) at which the observer at node \(j\) makes the observation.

The next \(m\) lines each contain two integers \(s_i\) and \(t_i\), representing the starting node and the target node of the \(i\)th player.

outputFormat

Output a single line with \(n\) integers. The \(j\)th integer is the number of players observed by the observer at node \(j\).

sample

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

1 2 1