For an undirected 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≤n,m,q,c≤105.
- 1≤u,v≤n.
- 0≤d≤10.
### Example
Input:
77121423364556673731512503
Output:
0112321
