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).
def  II():
    	return(int(input()))
def LMI():
	return(list(map(int,input().split())))
def I():
	return(input())
def MII():
	return(map(int,input().split()))
import sys
input=sys.stdin.readline
# import bisect
# import io,os
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from collections import Counter
# int(math.log(len(L)))
# import math
# from collections import defaultdict
mod=10**9+7
# from collections import deque
fact=[1]
for i in range(1,10**5+1):
    fact.append(fact[-1]*i%mod)



def t():
    n,m=MII()
    P=LMI()
    L=[0]*n
    I=[[] for _ in range(101)]
    for _ in range(m):
        l,r,k=MII()
        l-=1
        r-=1
        I[k].append((l,r))
    for k in range(100,-1,-1):
        for j in I[k]:
            l,r=j
            L[l]+=1
            if r<n-1:
                L[r+1]-=1
        for i in range(k+1,101):
            for l,r in I[i]:
                if r<n-1:
                    L[r+1]-=(fact[i-k+r-l]*pow(fact[i-k]*fact[r-l],-1,mod))%mod
        L[0]%=mod
        for i in range(1,n):
            L[i]+=L[i-1]
            L[i]%=mod
    for i in range(n):
        P[i]+=L[i]
    print(*P)












if __name__=="__main__":
# 	for _ in range(II()):
# 		t()
	t()
