Problem Statement

Given is a rooted tree with $N$ vertices numbered $1$ to $N$. The root is Vertex $1$, and the $i$-th edge $(1 \leq i \leq N - 1)$ connects Vertex $a_i$ and $b_i$.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value $0$.

Now, the following $Q$ operations will be performed:

• Operation $j$ $(1 \leq j \leq Q)$: Increment by $x_j$ the counter on every vertex contained in the subtree rooted at Vertex $p_j$.

Find the value of the counter on each vertex after all operations.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $1 \leq p_j \leq N$
• $1 \leq x_j \leq 10^4$
• The given graph is a tree.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex $1, 2, \ldots, N$ after all operations, in this order, with spaces in between.