Tô màu mảng

Bạn được cho một mảng gồm \(n\) phần tử chưa được tô màu. Ban đầu, mỗi phần tử có giá trị bằng \(0\).

Bạn cần xử lý \(q\) truy vấn dạng \((l, r, c)\) --- tô toàn bộ các phần tử từ chỉ số \(l\) đến \(r\) bằng màu \(c\). Mỗi truy vấn sẽ ghi đè lên các giá trị đã tô trước đó. Sau tất cả các truy vấn, hãy in ra màu cuối cùng của từng phần tử.

\InputFile

• Dòng đầu gồm hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^6\)) --- độ dài mảng và số truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(l, r, c\) --- truy vấn tô màu đoạn \([l, r]\) bằng màu \(c\)(\(1 \le l \le r \le n\), \(c \le 10^9\)).

\OutputFile
In ra trên 1 dòng \(n\) số nguyên, số thứ \(i\) chứa màu cuối cùng của phần tử ở vị trí \(i\).

\Scoring

• Có \(30\%\) số điểm ứng với \(n, q \le 1000\).
• Có \(30\%\) số điểm ứng với \(n, q \le 10^5\).
• \(40\%\) số điểm còn lại không có ràng buộc thêm.

Example

4 3
1 3 2
2 4 6
2 3 7

2 7 7 6