Вы главный разработчик в компании грузоперевозок Нурлаш и КО inc. Компании требуется, чтобы вы написали новый функционал для сортирующего робота. Робот контролирует n отсеков, последовательно пронумерованных от 1 до n, и может выполнять два типа операций:

1. Добавить контейнер с номером C в каждый отсек с L-го по R-ый

2. Убрать последний контейнер из каждого отсека с L-го по R-ый

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

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

Первая строка содержит два числа - n, m (1 ≤ n, m ≤ 105), количество отсеков и количество операций соответственно. Далее в m строках содержится по три числа L, R и C (1 ≤ L ≤ R ≤ 105, 0 ≤ C ≤ 109), описание операций. Если C = 0, то это операция второго типа, иначе - первого.

Все числа целые и в строках разделены ровно одним пробелом. Также гарантируется, что не будет операций допускающих удаление из пустых отсеков.

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

Выведите в единственной строке n чисел, разделенных пробелом. Первое число - номер последнего контейнера в первом отсеке, второе - во втором, и т.д. Если отсек пуст, выведите 0.