Codeforces Round 239 (Div. 1) |
---|
Закончено |
Задан массив, состоящий из 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
Название |
---|