A. Рыцарский турнир
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ура! Король Берлядии Берл II устраивает рыцарский турнир. Король уже разослал послание всем рыцарям королевства, а они, в свою очередь, дали согласие на участие в этом грандиозном событии.

Что же касается вас, то вы — простой крестьянин. Не удивительно, что рыцарский турнир вы проспали (ведь он проводился в выходной), и теперь вам очень хочется узнать его результаты. В этот раз рыцарский турнир в Берляндии проходил следующим образом:

  • В турнире принимали участие n рыцарей. Каждому рыцарю был присвоен уникальный номер — целое число от 1 до n.
  • Турнир проводился в m сражений, в i-ом сражении все еще не выбывшие рыцари с номерами не меньше li и не больше ri боролись за право продолжить участие в турнире.
  • После i-го сражения среди всех рыцарей, которые боролись, победил только один — рыцарь с номером xi, он продолжил участие в турнире. Остальные рыцари выбыли из турнира.
  • Победитель самого последнего (m-го) сражения (рыцарь с номером xm) был объявлен победителем всего турнира.

Вы узнали у своих друзей информацию про все сражения, и теперь для каждого рыцаря вам интересно знать, каким рыцарем он был побежден. Считается, что рыцарь с номером a победил рыцаря с номером b, если было такое сражение, в котором боролись оба этих рыцаря, а победителем из этого сражения вышел рыцарь с номером a.

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

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

В первой строке записано два целых числа n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) — количество рыцарей и количество сражений. В каждой из следующих m строк записано три целых числа li, ri, xi (1 ≤ li < ri ≤ n; li ≤ xi ≤ ri) — описание i-го сражения.

Гарантируется, что входные данные корректны и соответствуют условию задачи. Гарантируется, что в каждом сражении участвовали как минимум два рыцаря.

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

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

Примеры
Входные данные
4 3
1 2 1
1 3 3
1 4 4
Выходные данные
3 1 4 0
Входные данные
8 4
3 5 4
3 7 6
2 8 8
1 8 1
Выходные данные
0 8 4 6 4 8 6 1
Примечание

Рассмотрим первый тестовый пример. В первом сражении бились рыцари 1 и 2, победил рыцарь 1. Во втором сражении бились рыцари 1 и 3, победил рыцарь 3. В последнем сражении бились рыцари 3 и 4, победил рыцарь 4.