- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آقای هاشمی $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}$
ارسال پاسخ برای این سؤال