You are given a tree of $n$ vertices rooted at $1$. Each vertex has a number written on it, initially $0$.
There are $q$ queries, each of the form $(i, x)$, increasing each vertex in the subtree $i$ by $x$.
Find the number on each vertex after $q$ queries.
### Input
- The first line contain 2 integers $n$ and $q$.
- The next $n - 1$ lines, each line contains 2 integers $u$ and $v$, there is an edge between $u$ and $v$.
- The next $q$ lines, each line contains 2 integers $u, x$, a query.
### Output
- Print $n$ integers, the $i^{th}$ integers is the number on vertex $i$ after $q$ queries.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le u, v, i \le n$.
- $1 \le x \le 10^9$.
### Example
Input:
```
5 2
1 2
1 3
3 4
3 5
3 2
1 1
```
Output:
```
1 1 3 3 3
```
_Note: There exists another solution beside using Euler tour. Try to find it!_
