Fișierul intrare/ieșire:	trade.in, trade.out	Sursă	ad-hoc
Autor		Adăugată de	Andreescu Mihai •mihai995
Timp execuție pe test	1.1 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	5/5

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile trimise | Statistici

Trade

O regiune nordică s-a deschis recent comerțului liber. M negustori au decis să profite de această oportunitate și au decis să-și vândă produsele în N dintre orașele acestei regiuni. Orașele sunt așezate de-a lungul unui râu, în linie dreaptă, iar orașele sunt numerotate în ordine, de la 1 la N. Fiecare negustor își alege un interval [ai ; bi] de orașe în care va vinde un produs (unic – fiecare negustor are un produs unic). În plus, ei încep a-și vinde produsele de la prețul pi în orașul ai, dar pe măsură ce înaintează, devine mai lacom și crește prețul cu 1. Cu alte cuvinte, în orașul a va vinde cu p, în orașul a + 1 cu p + 1, … , iar în orașul b cu b – a + p.
Pentru a afla care e cel mai “de fiță” oraș, locuitorii vor să determine pentru orașul lor cât va costa cel mai scump produs adus de negustori. Pentru că ei nu știu să determine acest lucru, vă roagă să-I ajutați.

Date de intrare

În fișierul trade.in se vor găsi N și M, reprezentând numărul de orașe, respectiv numărul de negustori. Pe următoarele M linii, se vor afla câte 3 numere, a, b și p, reprezentând faptul că un negustor se extinde în intervalul [a ; b] și începe în orașul a cu prețul p.

Date de ieșire

În fișierul trade.out se vor găsi N numere. Al i-lea număr va reprezenta prețul celui mai scump produs din orașul i.

Restricții

• 1 <= N<= 1 000 000
• 1 <= M <= 300 000
• 1 <= a < b <= N
• 1 <= p <= 1 000 000 000
• Dacă într-un oraș nu vine niciun negustor, prețul pentru acel oraș va fi 0.
• Pentru 30% din teste, N, M <= 5 000
• Pentru alte 50% din teste, N <= 300 000

Exemplu