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 kbytes
Scorul tău	N/A	Dificultate	5/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile 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