Giải đấu hiệp sĩ

Có $n$ hiệp sĩ tham gia một giải đấu, được đánh số từ $1$ đến $n$. Giải đấu diễn ra qua $m$ trận đấu liên tiếp. Trong trận thứ $i$, tất cả những hiệp sĩ còn lại có số hiệu trong đoạn $[l_i,r_i]$ tham gia thi đấu. Sau trận, chỉ duy nhất hiệp sĩ số $x_i$ chiến thắng và tiếp tục giải; mọi hiệp sĩ còn lại trong đoạn $[l_i,r_i]$ bị loại.

Người chiến thắng của trận cuối cùng ($x_m$) là nhà vô địch của giải đấu.

Ta nói hiệp sĩ $a$ đánh bại hiệp sĩ $b$ nếu cả hai cùng tham gia một trận đấu và $a$ là người thắng trận đó. Với mỗi hiệp sĩ, hãy xác định ai là người đã đánh bại mình.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l_i$, $r_i$, $x_i$ — mô tả một trận đấu.

Dữ liệu đảm bảo hợp lệ và phù hợp với mô tả: tại mỗi trận luôn có ít nhất hai hiệp sĩ còn lại trong đoạn $[l_i,r_i]$, và $x_i$ là một trong số đó.

Dữ liệu ra

In ra $n$ số nguyên trên cùng một dòng. Số thứ $i$ là số hiệu hiệp sĩ đã đánh bại hiệp sĩ $i$. Nếu hiệp sĩ $i$ là nhà vô địch (không thua trận nào), in ra $0$.

Ràng buộc

• $2\le n\le 3·{10}^5$
• $1\le m\le 3·{10}^5$
• $1\le l_i<r_i\le n$
• $l_i\le x_i\le r_i$

Ví dụ