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

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

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

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

Входные данные Первая строка содержит два числа — n, m (1 ≤ n, m ≤ 10^5), количество отсеков и количество операций соответственно. Далее в m строках содержится по три числа L, R и C (1 ≤ L ≤ R ≤ 10^5, 0 ≤ C ≤ 10^9), описание операций. Если C = 0, то это операция второго типа, иначе — первого.

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

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

input: 5 3 1 5 1 2 4 0 4 5 10

output: 1 0 0 10 10