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.

Input

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$).

Output

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)$.