Problem: 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 <image> to each element a[j], where li ≤ j ≤ ri.

Record <image> 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 ≤ 105).

The second line contains n integers a[1], a[2], ..., a[n] (0 ≤ ai ≤ 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 <image> (1 ≤ li ≤ ri ≤ 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 (109 + 7).

Examples

Input

5 1
0 0 0 0 0
1 5 0


Output

1 1 1 1 1


Input

10 2
1 2 3 4 5 0 0 0 0 0
1 6 1
6 10 2


Output

2 4 6 8 10 7 3 6 10 15

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.*;
import java.lang.reflect.*;
import java.math.BigInteger;
import static java.math.BigInteger.*;
import java.security.CodeSource;
import java.security.KeyStore;
import java.util.*;
import java.util.jar.JarEntry;
import java.util.jar.JarFile;
import java.util.logging.Level;
import java.util.logging.Logger;

// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display

public class Main {

    private void run() throws Exception {
        err = System.err;
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }
        
        if( oj ){
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        }
        else{
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch ( IOException e) {
                MLE();
            }
        }
        solve();
        
        out.flush();
    }
    
    FastScanner sc;
    PrintWriter out;
    PrintStream err;
    
    
    void MLE(){
        int[][] arr = new int[1024*1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024*1024];
        }
    }

    class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStreamReader reader) {
            br = new BufferedReader(reader);
            st = new StringTokenizer("");
        }

        String next() {
            while( !st.hasMoreElements() )
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException ex) {
                    MLE();
                }
            return st.nextToken();
        }
        
        int nextInt(){ return Integer.parseInt(next());}
    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    //-------------------------------------------------------------------//
    
    class Seg{
        int l, r;

        Seg(int _l, int _r) {
            l = _l;
            r = _r;
        }
    }
    
    long add( long a, long b ){
        long c = a + b;
        while( c < 0 ) c += mod;
        while( mod <= c ) c -= mod;
        return c;
    }
    
    long sub( long a, long b ){
        long c = a - b;
        while( c < 0 ) c += mod;
        while( mod <= c ) c -= mod;
        return c;
    }
    
    final int mod = (int)1e9 + 7, maxK = 100;  
    int n, m;
    long[] arr, ans;
    ArrayList<Seg>[] seg;
    long[] fact, invFact;
    {
        fact = new long[(int)1e5+100];
        fact[0] = 1;
        for (int i = 1; i < fact.length; i++) {
            fact[i] = fact[i-1] * i % mod;
        }
        invFact = new long[fact.length];
        invFact[fact.length-1] = valueOf(fact[fact.length-1]).modInverse(valueOf(mod)).intValue();
        for (int i = invFact.length-2; 0<=i; i--) {
            invFact[i] = invFact[i+1] * (i+1) % mod;
        }
    }
    
    long C( int m, int n ){
        if(!( m <= n )) 
            MLE();
        return fact[n] * invFact[m] % mod * invFact[n-m] % mod;
    }
    
    void solve(){
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new long[n+1];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        seg = new ArrayList[maxK+1];
        for (int i = 0; i < seg.length; i++) {
            seg[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            Seg s = new Seg(sc.nextInt()-1,sc.nextInt()-1);
            seg[sc.nextInt()].add(s);
        }
        
        ans = new long[n];
        
        for (int cntTake = maxK; 0 <= cntTake; --cntTake) {
            for( Seg s : seg[cntTake] ){
                ++ans[s.l];
            }
            
            for (int i = cntTake; i <= maxK; i++) {
                for( Seg s : seg[i] ){
                    if( s.r+1 < n ){
                        ans[s.r+1] = sub( ans[s.r+1], C( i-cntTake, s.r-s.l + i-cntTake) );
                    }
                }
            }
            
            for (int i = 1; i < n; i++) {
                ans[i] = add( ans[i-1], ans[i] );
            }
        }

        for (int i = 0; i < n; i++) {
            out.print( " " + add(ans[i],arr[i]) );
        }
        out.println();
    }
    
}