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.

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$
```

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

-   $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.

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

• Operation $1$: Increment by $10$ the counter on every vertex contained in the subtree rooted at Vertex $2$, that is, Vertex $2, 3, 4$. The values of the counters on Vertex $1, 2, 3, 4$ are now $0, 10, 10, 10$, respectively.
• Operation $2$: Increment by $100$ the counter on every vertex contained in the subtree rooted at Vertex $1$, that is, Vertex $1, 2, 3, 4$. The values of the counters on Vertex $1, 2, 3, 4$ are now $100, 110, 110, 110$, respectively.
• Operation $3$: Increment by $1$ the counter on every vertex contained in the subtree rooted at Vertex $3$, that is, Vertex $3$. The values of the counters on Vertex $1, 2, 3, 4$ are now $100, 110, 111, 110$, respectively.