For a directed graph consisting of $n$ vertices and $m$ edges, define the distance between vertex $u$ and vertex $v$ as the minimum number of edges in a path from $u$ to $v$.
Initially, all vertices are colored $0$. You are given $q$ queries, each of which asks to color all vertices within a distance of at most $d$ from vertex $u$ with color $c$. Find the color of each vertex after all queries are processed.
### Input
- The first line contains three integers $n, m, q$.
- The next $m$ lines each contain two integers $u, v$, representing an edge between vertex $u$ and vertex $v$ in the graph.
- The next line contains an integer $q$, the number of queries.
- The next $q$ lines each contain three integers $u, d, c$.
### Output
- Print $n$ lines, where the $i$-th line contains the color of vertex $i$ after all $q$ queries.
### Constraints
- $1 \le n, m, q, c \le 10^5$.
- $1 \le u, v \le n$.
- $0 \le d \le 10$.
### Example
Input:
```
7 7
1 2
1 4
2 3
3 6
4 5
5 6
6 7
3
7 3 1
5 1 2
5 0 3
```
Output:
```
0
1
1
2
3
2
1
```
