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.util.*;

public class C {
	public static void main (String[] args) { new C(); }

	public C() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		work();
		
		int n = fs.nextInt();
		int q = fs.nextInt();
		int[] a = fs.nextIntArray(n);
		
		int[][] sums = new int[101][n];
		for(int i = 0; i < q; i++) {
			
			int L = fs.nextInt()-1, R = fs.nextInt()-1;
			int K = fs.nextInt();
			int len = R-L+1, other = 0;
			
			sums[K][L] = add(sums[K][L], 1);
			for(int j = K; j >= 0; j--, other++) {
				if(R+1 < n) {
					sums[j][R+1] = sub(sums[j][R+1], choose(len+other-1, other));
				}
			}
		}
		
		int[][] fin = new int[101][n];
		for(int i = 100; i >= 0; i--) {
			for(int j = 0; j < n; j++) {
				fin[i][j] = sums[i][j];
				if(j > 0) fin[i][j] = add(fin[i][j], fin[i][j-1]);
				if(i+1 <= 100) fin[i][j] = add(fin[i][j], fin[i+1][j]);
			}
		}
		
		for(int i = 0; i < n; i++) {
			a[i] = add(a[i], fin[0][i]);
		}
		
		for(int i = 0; i < n; i++) {
			out.print(a[i] + " ");
		}
		
		out.close();
	}
	
	int MOD = (int)1e9+7;
	int[] fact, invFact;
	void work() {
		int MAX = 100100;
		fact = new int[MAX];
		fact[0] = 1;
		for(int i = 1; i < MAX; i++) {
			fact[i] = mult(fact[i-1], i);
		}
		
		int[] invs = new int[MAX];
		invs[0] = invs[1] = 1;
		for(int i = 2; i < invs.length; i++) {
			invs[i] = sub(MOD, mult(MOD/i, invs[MOD%i]));
		}
		
		invFact = new int[MAX];
		invFact[0] = invs[0];
		for(int i = 1; i < MAX; i++) {
			invFact[i] = mult(invFact[i-1], invs[i]);
		}
		
	}
	
	int choose(int n, int k) {
		int num = fact[n];
		int den = mult(invFact[k], invFact[n-k]);
		return mult(num, den);
	}
	
	int add(int a, int b) {
		a += b;
		if(a >= MOD) a -= MOD;
		return a;
	}
	int mult(long a, long b) {
		a *= b;
		if(a >= MOD) a %= MOD;
		return (int)a;
	}
	int sub(int a, int b) {
		a -= b;
		if(a < 0) a += MOD;
		return a;
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}