Cho một đơn đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh. Độ dài của mỗi cạnh là ~1~. Ta định nghĩa khoảng cách giữa hai đỉnh ~u~ và ~v~ là độ dài đường đi ngắn nhất từ ~u~ đến ~v~.

Ban đầu, tất cả các đỉnh được tô màu ~0~. Cho ~Q~ truy vấn, truy vấn thứ ~i~ yêu cầu tô màu ~c_i~ cho tất cả các đỉnh có khoảng cách đến ~u_i~ nhỏ hơn hoặc bằng ~d_i~. Hãy cho biết màu của từng đỉnh sau khi thực hiện xong ~Q~ truy vấn trên.

Input

• Dòng đầu ghi hai số nguyên dương ~N, M~ ~(N, M \le 10^5)~ - số đỉnh và số cạnh của đồ thị.
• ~M~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i, v_i \le N)~ mô tả một cạnh trong đồ thị. Dữ liệu vào đảm bảo đồ thị đã cho là đơn đồ thị.
• Dòng tiếp theo ghi số nguyên dương ~Q~ ~(Q \le 10^5)~ - số truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u_i, d_i, c_i~ ~(1 \le u_i \le N,~ ~0 \le d_i \le 10,~ ~1 \le c_i \le 10^5)~.

Output

• In ra ~N~ dòng, dòng thứ ~i~ in ra một số nguyên duy nhất - màu của đỉnh ~i~ sau khi thực hiện ~Q~ truy vấn trên.

Samples

Sample Input 1

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

Sample Output 1

0
1
1
2
3
2
1

Clarification

Hình vẽ mô tả ví dụ. Trong hình vẽ, các đỉnh màu ~0~ được để trắng, các đỉnh màu ~1~ được tô xanh dương, các đỉnh màu ~2~ được tô vàng, các đỉnh màu ~3~ được tô xanh lá cây.

Scoring

• ~50\%~ số test tương ứng với ~50\%~ số điểm có ~N, M, Q \le 2000~
• ~50\%~ số test còn lại không có ràng buộc gì thêm