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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

/**
 * Created by hama_du on 2014/09/27.
 */
public class ProblemC {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int W = 120;

        int n = in.nextInt();
        int q = in.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }


        prec(110000);


        long[][] table = new long[W+1][n+W+10];
        while (--q >= 0) {
            int l = in.nextInt();
            int r = in.nextInt()+1;
            int k = in.nextInt();
            table[W-k][l] += 1;
            table[W-k][l] %= MOD;
            int p = 0;
            for (int w = W-k ; w <= W ; w++) {
                table[w][r] += (MOD - comb(r-l-1+p, p));
                table[w][r] %= MOD;
                p++;
            }
        }

        for (int i = 0 ; i <= W ; i++) {
            for (int j = 0 ; j < n+W+10 ; j++) {
                if (i >= 1) {
                    table[i][j] += table[i-1][j];
                }
                if (j >= 1) {
                    table[i][j] += table[i][j-1];
                }
                table[i][j] %= MOD;
            }
        }


        StringBuilder b = new StringBuilder();
        for (int i = 0 ; i < n ; i++) {
            b.append(' ').append((table[W][i+1] + a[i]) % MOD);
        }
        out.println(b.substring(1));
        out.flush();
    }


    public static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }


    static final int MOD = 1000000007;

    static long[] _fact;
    static long[] _invfact;
    static long comb(long ln, long lr) {
        int n = (int)ln;
        int r = (int)lr;
        if (n < 0 || r < 0 || r > n) {
            return 0;
        }
        if (r > n / 2) {
            r = n - r;
        }
        return (((_fact[n] * _invfact[n - r]) % MOD) * _invfact[r]) % MOD;
    }

    static void prec(int n) {
        _fact = new long[n + 1];
        _invfact = new long[n + 1];
        _fact[0] = 1;
        _invfact[0] = 1;
        for (int i = 1; i <= n; i++) {
            _fact[i] = _fact[i - 1] * i % MOD;
            _invfact[i] = inv(_fact[i]);
        }
    }

    static long pow(long a, long x) {
        long res = 1;
        while (x > 0) {
            if (x % 2 != 0) {
                res = (res * a) % MOD;
            }
            a = (a * a) % MOD;
            x /= 2;
        }
        return res;
    }

    static long inv(long a) {
        return pow(a, MOD - 2) % MOD;
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}