Given a tree of $n$ vertices rooted at $1$. Each vertice has a number, which is $0$ initially.
There are $q$ queries, they ask you, for every vertice on the simple path from $x$ to $y$, if the value on this vertice is $0$, assign $z$ to it. It is guaranteed that $x$ is an ancestor of $y$.
Find the number on each vertice after $q$ queries.
### Input
- The first line contain 2 integers $n, q$.
- The next $n - 1$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$.
- The next $q$ lines, each line contains 3 integers $x, y, z$, a query.
### Output
- Print $n$ integers, the $i^{th}$ number is number on vertice $i$.
### Constraints
- $1 \le n, q, y \le 10^5$.
- $1 \le u, v, x \le n$.
### Example
Input:
```
5 3
1 2
2 3
2 4
1 5
1 3 1
1 4 2
1 2 3
```
Output:
```
1 1 1 2 0
```
