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

حل سؤال در بانک سؤالات