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*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub>. Query *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub> means that we should add <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8f3ef957f9a1ec49b3350880600f501fb3c21130.png" style="max-width: 100.0%;max-height: 100.0%;"/> to each element *a*[*j*], where *l*<sub class="lower-index">*i*</sub> ≤ *j* ≤ *r*<sub class="lower-index">*i*</sub>.

Record <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/d91fc7a27ef531ef9ddb1523f8c0a6c252cb7fd9.png" style="max-width: 100.0%;max-height: 100.0%;"/> 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<sup class="upper-index">5</sup>).

The second line contains *n* integers *a*[1], *a*[2], ..., *a*[*n*] (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the initial array.

Next *m* lines contain queries in the format *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *k*<sub class="lower-index">*i*</sub> — to all elements of the segment *l*<sub class="lower-index">*i*</sub>... *r*<sub class="lower-index">*i*</sub> add number <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8f3ef957f9a1ec49b3350880600f501fb3c21130.png" style="max-width: 100.0%;max-height: 100.0%;"/> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*; 0 ≤ *k* ≤ 100).
from math import factorial as fact
try:
 def binomial(ai,bi):
    ai=ai%100005
    bi=bi%100005
    m=(fact(ai)//fact(bi)//fact(ai-bi))%1000000007
    return m

 n,m=map(int,input().split())
 Ai=list(map(int,input().split()))
 while m>0:
    li,ri,qi=map(int,input().split())
    for j in range(li,ri+1):
        Ai[j-1]+=binomial(j-li+qi,qi)
    m-=1
 for i in Ai:
    print(i%1000000007,end=" ")
except:pass