C. Занимательный массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задан массив, состоящий из n целых чисел: a[1], a[2], ..., a[n]. Более того, заданы m запросов, каждый из которых характеризуется тремя числами li, ri, ki. Запрос li, ri, ki обозначает, что нужно добавить к каждому элементу a[j], где li ≤ j ≤ ri, число Ckij - li + ki.

Запись Cxy обозначает биномиальный коэффициент, или количество сочетаний из y элементов по x элементов.

Вам нужно выполнить последовательно все запросы и вывести, чему будут равны элементы массива в итоге, после всех запросов.

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

В первой строке заданы целые числа n, m (1 ≤ n, m ≤ 105).

Во второй строке задано n целых чисел a[1], a[2], ..., a[n] (0 ≤ ai ≤ 109) — изначальное состояние массива.

В следующих m строках заданы запросы в формате li, ri, ki — прибавить всем элементам отрезка li... ri число Ckij - li + ki (1 ≤ li ≤ ri ≤ n; 0 ≤ k ≤ 100).

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

Выведите n целых чисел: i-е число — это значение элемента a[i] после всех запросов. Так как значения могут быть достаточно большими выводите их по модулю 1000000007 (109 + 7).

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