A9424 | Curious Array

You've got an array consisting of $n$ integers: $a[1],a[2],...,a[n]$ . Moreover, there are $m$ queries, each query can be described by three integers $l_{i},r_{i},k_{i}$ . Query $l_{i},r_{i},k_{i}$ means that we should add  to each element $a[j]$ , where $l_{i}<=j<=r_{i}$ .

Record  means the binomial coefficient, or the number of combinations from $y$ elements into groups of $x$ elements.

You need to fulfil consecutively all queries and then print the final array.

The first line contains integers $n$ , $m$ ( $1<=n,m<=10^{5}$ ).

The second line contains $n$ integers $a[1],a[2],...,a[n]$ ( $0<=a_{i}<=10^{9}$ ) — the initial array.

Next $m$ lines contain queries in the format $l_{i},r_{i},k_{i}$ — to all elements of the segment $l_{i}...\ r_{i}$ add number  ( $1<=l_{i}<=r_{i}<=n$ ; $0<=k<=100$ ).

Print $n$ integers: the $i$ -th number is the value of element $a[i]$ after all the queries. As the values can be rather large, print them modulo $1000000007$ $(10^{9}+7)$ .