e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - March 7 - Segment Tree

Торговля

Вдоль трассы Алматы-Тараз есть n населенных пунктов, пронумерованных числами от 1 до n. В начале зимы m неизвестных торговцев привезли из неизвестного аула вязаные шапки и начали ими торговать в этих населенных пунктах. У этих торговцев есть два принципа: не торговать в одном месте более одного раза (один день) и с каждым днем увеличивать цену на шапку.

Более формально каждый i-ый торговец:

  • Начинает торговать в населенном пункте li со стартовой ценой на одну шапку xi
  • Каждый день переходит в соседний населенный пункт, то есть, если вчера он торговал в населенном пункте j, то сегодня торгует в населенном пункте j + 1
  • Каждый день увеличивает цену на 1, то есть, если вчера цена на его шапки была x, то сегодня цена x + 1
  • Завершает торговать в населенном пункте ri (при этом в пункте ri торговля происходит).

Наша задача для каждого населенного пункта определить максимальную цену на одну шапку за всю историю.

Входные данные

В первой строке находятся два целых числа n (1n300000) и m (1m300000) количество населенных пунктов и количество торговцев соответственно.

В каждой из следующих m строк находятся по три целых числа li, ri (1 ≤ lirin) и xi (1xi109) - номера начального и конечного населенных пунктов и начальная цена на шапку для i-го торговца соответственно.

Выходные данные

Выведите n целых чисел, разделенных пробелом,  где i-ое число равно максимальной цене на одну шапку за всю историю продаж i-ого населенного пункта. Если в каком-то населенном пункте никто не торговал шапками, то для этого населенного пункта выведите 0.

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
5 2
1 3 2
2 4 6
Вихідні дані #1
2 6 7 8 0
Вхідні дані #2
6 4
4 4 3
1 2 5
5 6 1
6 6 1
Вихідні дані #2
5 6 0 3 1 2
Джерело 2013 IX Международная Жаутыковская Олимпиада Алматы, Казахстан, 16 января