Giáo sư X đang thử nghiệm Robot tô màu cho ~N~ bức tranh đánh số lần lượt từ ~1~ đến ~N~. Ban đầu ~N~ bức tranh chưa được tô màu gì. Robot sẽ thực hiện ~Q~ thao tác tô màu, mỗi thao tác Robot sẽ tô màu ~c~ cho đoạn liên tiếp các bức tranh từ ~l~ đến ~r~. Nếu vị trí ~i~ đã được tô màu thì sau lần tô màu ~c~ này, vị trí ~i~ sẽ có màu mới là ~c~.

Yêu cầu: Giáo sư X rất muốn biết sau ~Q~ thao tác tô màu như trên thì màu của mỗi bức tranh là màu gì.

Input

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ ~(N,Q \le 10^5)~;

• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l,r,c~ mô tả một thao tác tô màu của Robot ~(c \le 10^6)~.

Output

Ghi ra một dòng duy nhất gồm ~N~ số, số thứ ~i~ thể hiện màu được tô ở bức tranh thứ ~i~. Nếu bức tranh chưa được tô màu nào thì in ra ~0~.

Sample Input 1

5 6
2 3 2
1 1 6
3 4 9
3 5 7
2 3 6
2 4 3

Sample Output 1

6 3 3 3 7