Диспетчер ведёт расписание из n последовательных интервалов. Изначально для каждого интервала надбавка равна 0.

Затем поступает m распоряжений. Каждое распоряжение задаётся тройкой l, r, v и означает, что ко всем интервалам с номерами от l до r включительно нужно прибавить надбавку v.

Требуется применить все распоряжения и вывести итоговые надбавки для всех n интервалов.

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

Первая строка содержит два целых числа n и m — количество интервалов расписания и количество распоряжений.

Каждая из следующих m строк содержит три целых числа l, r, v — границы диапазона и величину надбавки.

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

Выведите n целых чисел через пробел — итоговые надбавки для интервалов с 1 по n.

Ограничения

• 1 <= n, m <= 2 * 10^5
• 1 <= l <= r <= n
• -10^9 <= v <= 10^9

Итоговые значения могут не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

1 1
1 1 0

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

0

Пример 2

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

5 5
1 5 3
2 4 -2
3 3 7
1 1 -5
5 5 4

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

-2 1 8 1 7