• محدودیت زمان: ۱.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

آقای هاشمی $n$ گونی خالی در یک ردیف کنار هم گذاشته است. او گونی‌ها را با اعداد $1$ تا $n$ به ترتیب از چپ به راست شماره‌گذاری کرده است.

او می‌خواهد در $m$ عملیات در این گونی‌ها مهره بریزد. او در عملیات $i$ام سه عدد $l_i$، $r_i$ و $x_i$ را انتخاب می‌کند و سپس در همه‌ی گونی‌های بازه‌ی $[l_i, r_i]$ یک مهره $x_i$ می‌اندازد.

آقای هاشمی می‌خواهد بعد از پایان این $m$ عملیات، برای هر گونی، کوچک‌ترین عددی که هیچ مهره‌ای با آن شماره در آن گونی نیست را حساب کند.

ورودی

در سطر اول ورودی دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده است. $$1 \leq n, m \leq 500 , 000$$ در $m$ سطر بعدی در هر سطر، سه عدد $l_i$، $r_i$ و $x_i$ که با یک فاصله از هم جدا شده‌اند به ترتیب می‌آیند.

$$1 \leq l_i \leq r_i \leq n, \quad \quad 1 \leq x_i \leq 10^9$$

خروجی

در تنها سطر خروجی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند چاپ کنید. عدد $i$ام نشان دهنده‌ی پاسخ مسئله برای گونی $i$ام است.

مثال

ورودی نمونه ۱

3 2
1 2 1
2 3 2

خروجی نمونه ۱

2 3 1

بعد از پایان این عملیات‌ها وضعیت مهره‌ها در هر گونی به صورت زیر است:

• گونی $1$: ${1}$
• گونی $2$: ${2, 1}$
• گونی $3$: ${2}$

ورودی نمونه ۲

5 8
1 3 1
3 3 4
1 2 1
5 5 1
4 5 5
2 5 3
1 5 2
3 4 3

خروجی نمونه ۲

3 4 5 1 4

بعد از پایان این عملیات‌ها وضعیت مهره‌ها در هر گونی به صورت زیر است:

• گونی $1$: ${1, 1, 2}$
• گونی $2$: ${1, 1, 3, 2}$
• گونی $3$: ${1, 4, 3, 2, 3}$
• گونی $4$: ${5, 3, 2, 3}$
• گونی $5$: ${1, 5, 3, 2}$