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 li,ri,ki. Query li,ri,ki means that we should add to each element a[j], where li \le j \le ri.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 \le n,m \le 105).The second line contains n integers a[1],a[2],...,a[n] (0 \le ai \le 109)- the initial array.Next m lines contain queries in the format li,ri,ki- to all elements of the segment li... ri add number (1 \le li \le ri \le n; 0 \le k \le 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 (109+7).