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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  if (c == '-') f = 1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
inline void scf(T1 &x, T2 &y) {
  scf(x);
  scf(y);
}
template <typename T1, typename T2, typename T3>
inline void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
inline void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  scf(w);
}
template <typename T>
inline bool chkmin(T &x, const T &y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmax(T &x, const T &y) {
  return x < y ? x = y, 1 : 0;
}
const int maxn = 1e5 + 100;
const int maxk = 110;
const int mod = 1e9 + 7;
int n, q;
int a[maxn], b[maxn][maxk], dlt[maxn][maxk], foo[maxn][maxk];
int fac[maxn << 1], rfac[maxn << 1];
inline int SUM(const int &x, const int &y) {
  return x + y < mod ? x + y : x + y - mod;
}
inline void ADD(int &x, const int &y) { x = x + y < mod ? x + y : x + y - mod; }
inline int pow_mod(int x, int n) {
  int ret = 1;
  while (n) {
    if (n & 1) ret = 1ll * ret * x % mod;
    x = 1ll * x * x % mod;
    n >>= 1;
  }
  return ret;
}
inline int C(int n, int m) {
  return 1ll * fac[n] * rfac[m] % mod * rfac[n - m] % mod;
}
int main() {
  rfac[0] = fac[0] = 1;
  for (int i = (1); i <= (maxn + maxn - 1); ++i)
    fac[i] = 1ll * fac[i - 1] * i % mod;
  rfac[maxn + maxn - 1] = pow_mod(fac[maxn + maxn - 1], mod - 2);
  for (int i = (maxn + maxn - 1); i >= (2); --i)
    rfac[i - 1] = 1ll * rfac[i] * i % mod;
  scf(n, q);
  for (int i = (1); i <= (n); ++i) scf(a[i]);
  while (q--) {
    int l, r, k;
    scf(l, r, k);
    ADD(dlt[l][k], 1);
    if (!k)
      ADD(dlt[r + 1][k], mod - 1);
    else {
      for (int i = (r + 1); i <= (r + k + 1); ++i) {
        if (i > n) break;
        ADD(dlt[i][i - r], mod - C(r - l + 1 + k, k - (i - r) + 1));
        ADD(dlt[i + 1][i - r], C(r - l + 1 + k, k - (i - r) + 1));
      }
    }
  }
  for (int k = (0); k <= (101); ++k)
    for (int i = (1); i <= (n); ++i) ADD(dlt[i][k], dlt[i - 1][k]);
  for (int k = (101); k >= (0); --k) {
    for (int i = (1); i <= (n); ++i)
      ADD(b[i][k], SUM(b[i - 1][k], b[i][k + 1]));
    for (int i = (1); i <= (n); ++i) ADD(b[i][k], dlt[i][k]);
  }
  for (int i = (1); i <= (n); ++i) printf("%d ", (a[i] + b[i][0]) % mod);
  return 0;
}