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 <class _T>
inline void ina(_T a[], int n) {
  for (int i = 0; i < n; i++) In(a[i]);
}
int TEST_CASE = 0;
template <class _T>
inline _T pow(_T a, _T b, _T m) {
  a %= m;
  _T ans = 1 % m;
  while (b) {
    if (b & 1) ans *= a, ans %= m;
    a *= a;
    a %= m;
    b >>= 1;
  }
  return ans;
}
template <class _T>
inline _T pow(_T a, _T b) {
  _T ans = 1;
  while (b) {
    if (b & 1) ans *= a;
    a *= a;
    b >>= 1;
  }
  return ans;
}
template <class _T>
inline _T add(_T a, _T b, _T m) {
  return a >= m - b ? a - (m - b) : a + b;
}
template <class _T>
inline _T multiply(_T a, _T b, _T m) {
  _T ans = 0;
  if (b > a) swap(a, b);
  while (b) {
    if (b & 1) ans = add(ans, a, m);
    b >>= 1;
    a = add(a, a, m);
  }
  return ans;
}
template <class _T>
inline _T bigpow(_T a, _T b, _T m) {
  a %= m;
  _T ans = 1 % m;
  while (b) {
    if (b & 1) ans = multiply(ans, a, m);
    a = multiply(a, a, m);
    b >>= 1;
  }
  return ans;
}
template <class _T>
inline _T modinvers(_T a, _T m) {
  return m > 2000000000LL ? bigpow(a, m - 2, m) : pow(a, m - 2, m);
}
template <class _T>
_T _egcd(_T a, _T b, _T &x, _T &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  _T _g = _egcd(b, a % b, x, y);
  _T xt = x;
  x = y, y = xt - (a / b) * y;
  return _g;
}
template <class _T>
inline _T fmodinvers(_T a, _T m) {
  _T x, y;
  _egcd(a, m, x, y);
  x %= m;
  if (x < 0) x += m;
  return x;
}
template <class _T>
inline _T _lcm(_T a, _T b) {
  return (a * b) / __gcd(a, b);
}
template <class T>
inline T SQ(T a) {
  return a * a;
}
long long SQRT(long long n) {
  long long e = sqrt(n * 1.0);
  long long l = max(0LL, e - 2), r = min(n, e + 2);
  long long ans = 0;
  while (l <= r) {
    long long m = ((l + r) >> 1);
    if (m * m <= n)
      ans = m, l = m + 1;
    else
      r = m - 1;
  }
  return ans;
}
long long CBRT(long long n) {
  long long e = cbrt(n * 1.0);
  long long l = max(0LL, e - 2), r = min(n, e + 2);
  long long ans = 0;
  while (l <= r) {
    long long m = ((l + r) >> 1);
    if (m * m * m <= n)
      ans = m, l = m + 1;
    else
      r = m - 1;
  }
  return ans;
}
const long double EPS = 1e-9;
const long double PI = acos(-1.0);
const int SIZE = 1e6;
long long mod = 1e9 + 7;
long long fc[100500], ifc[100500];
long long ncr(int n, int r) {
  return (((fc[n] * ifc[r]) % mod) * ifc[n - r]) % mod;
}
long long a[102][100002], b[100002];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, k, l, r;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> b[i];
  fc[0] = ifc[0] = 1;
  for (int i = 1; i <= n + 100; i++) {
    fc[i] = (i * fc[i - 1]) % mod;
    ifc[i] = modinvers(fc[i], mod);
  }
  while (m--) {
    cin >> l >> r >> k;
    a[k][l]++;
    for (int p = r - l, i = 0; k >= 0; k--, i++) {
      a[k][r + 1] -= ncr(p + i, i), a[k][r + 1] %= mod;
    }
  }
  for (k = 100; k >= 0; k--)
    for (int i = 1; i <= n; i++)
      a[k][i] = (a[k][i] + a[k][i - 1] + a[k + 1][i]) % mod;
  for (int i = 1; i <= n; i++)
    cout << ((b[i] + a[0][i]) % mod + mod) % mod << " ";
  cout << "\n";
  return 0;
}