+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن ها در طی جهان‌گردی‌شان با مسائلی روبه رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید.*  هنگام ورود به تهران، وقتی که چرزه و پشمک دیگر فکر می‌کردند که کارشان را با موفقیت انجام داده‌اند، ناگهان $q$ مرد خشمگین ظاهر شدند و از آن دو (که دیگر حسابی معروف شده‌بودند!) خواستند که بهشان یادگاری بدهند. چرزه و پشمک که می‌دانستند اگر یادگاری ندهند، حتما می‌میرند، بنابراین تصمیم گرفتند که یک دنباله از اعداد طبیعی به طول $n$ به عنوان یادگاری به آن ها بدهند. وقتی که چرزه و پشمک این را به آن $q$ مرد خشمگین گفتند، هرکدام از آن ها یک خواهش از چرزه و پشمک کردند. هر خواهش با سه عدد $l$ و $r$ و $k$ بیان می شود و این بدین معنا است که آن فرد خشمگین می‌خواهد که آنتروپرولارت دنباله‌ی $a_l, a_{l+1}, a_{l+2}, ..., a_r$ دقیقا برابر با $k$ باشد. (فرض کنید که دنباله‌ی $a$، یادگاری چرزه و پشمک باشد.) توجه کنید که آنتروپرولارت یک دنباله، برابر با کمینه‌ی تعداد زیردنباله‌های **متوالی** از دنباله است که این شرایط را رعایت بکنند: 1. هر عضو از دنباله در **دقیقا یکی** از زیردنباله‌ها باشد. 2. اعداد هر زیردنباله به ترتیب اکیدا صعودی باشند. برای مثال آنتروپرولارت دنباله‌ی $\left[5, 7, 2, 3, 1 \right]$ برابر با $3$ می‌باشد و زیردنباله‌های متوالی عبارت هستند از: $\left[5, 7\right], \left[2, 3 \right], \left[1 \right]$ چرزه و پشمک می‌دانند که محبوبیت آنتروپرولارت جوری است که اگر به این خواهش‌ها توجه نشود، آن افراد آن‌ها را خواهند کشت. (این اصل به عنوان یک اصل معروف در کتاب زمینه‌ی جامعه شناسی اگ برن و نیم کف آورده‌شده‌است!) بنابراین آن ها تصمیم دارند که دنباله‌ای بسازند که به تمام این خواهش‌ها توجه شود. هم چنین از آن‌جایی که احتمالا تا الان فهمیده‌اید پشمک و چرزه کمی تنبل هستند و حال ندارند اعداد بزرگ را بنویسند بنابراین آن‌ها دنباله‌ای را با این شرایط می‌خواهند که $\max_{1 \leq i \leq |a|} a_i$ کمینه باشد. اما آن ها وقت ندارند که دنباله را خودشان بنویسند بنابراین ... # ورودی در خط اول دو عدد $n$ و $q$ آورده‌شده‌است که به ترتیب نمایانگر طول دنباله‌ی خواسته‌شده و تعداد افراد خشمگین است. در $q$ خط بعد، در هر خط به ترتیب از چپ به راست سه عدد $l$ و $r$ و $k$ داده می‌شود که نمایانگر خواهش فرد $i$ ام است. $$1 \leq n \leq 200$$ $$1 \leq q \leq \frac{n(n+1)}{2} $$ $$1 \leq l \leq r \leq n, 1 \leq k \leq n$$ # خروجی اگر هیچ روشی برای درست کردن چنین دنباله‌ای نیست، عبارت `-1` را چاپ کنید در غیر این‌صورت در یک خط $n$ عدد چاپ کنید که دنباله‌ای است که به تمام خواهش‌ها پاسخ بدهد و بزرگ‌ترین عدد در آن، کمینه‌ی ممکن باشد. **از آن جایی که ممکن است برای یک حالت، چندین جواب وجود داشته باشد شما، یکی را به دلخواه چاپ کنید!** # مثال ## ورودی نمونه ۱ ``` 3 3 1 2 2 1 3 2 2 3 1 ``` ## خروجی نمونه ۱ ``` 1 1 2 ``` ## ورودی نمونه ۲ ``` 4 2 1 2 1 1 3 3 ``` ## خروجی نمونه ۲ ``` -1 ```