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;
const int inf = 2000000000;
static inline int Rint() {
  struct X {
    int dig[256];
    X() {
      for (int i = '0'; i <= '9'; ++i) dig[i] = 1;
      dig['-'] = 1;
    }
  };
  static X fuck;
  int s = 1, v = 0, c;
  for (; !fuck.dig[c = getchar()];)
    ;
  if (c == '-')
    s = 0;
  else if (fuck.dig[c])
    v = c ^ 48;
  for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48))
    ;
  return s ? v : -v;
}
template <typename T>
static inline void cmax(T& a, const T& b) {
  if (b > a) a = b;
}
template <typename T>
static inline void cmin(T& a, const T& b) {
  if (b < a) a = b;
}
const int mod = 1000000007;
static inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
static inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
static inline int mul(long long a, long long b) { return a * b % mod; }
static inline int cal_inv(long long x) {
  int n = mod - 2;
  long long ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * x % mod;
    x = x * x % mod;
  }
  return ret;
}
int inv[100005];
static inline int cal_comb(int a, int b) {
  if (b > a || b < 0) return 0;
  if (b == a || b == 0) return 1;
  int ret = 1;
  for (int x = a - b + 1, y = 1; x <= a; ++x, ++y) {
    ret = mul(ret, x);
    ret = mul(ret, inv[y]);
  }
  return ret;
}
void init() {
  for (int i = 1; i < 100005; ++i) inv[i] = cal_inv(i);
}
int data[100005];
struct Pt {
  int pos, a, b, flag, mul;
  int operator<(const Pt& o) const {
    if (pos != o.pos) return pos < o.pos;
    return flag > o.flag;
  }
};
int dp[105];
Pt cmd[100005 * 2];
int main() {
  init();
  int n = Rint(), m = Rint();
  for (int i = (1); i < (n + 1); ++i) data[i] = Rint();
  int top = 0;
  int maxk = 0;
  ++maxk;
  while (m--) {
    int l = Rint(), r = Rint(), k = Rint();
    int start = r - k + 1;
    if (start < l) start = l;
    int a = start - l + k;
    int b = start - l;
    int curr = cal_comb(a, a - b);
    for (int i = start; i <= r; ++i, ++a) {
      data[i] = add(data[i], curr);
      curr = mul(curr, a + 1);
      curr = mul(curr, inv[a - k + 1]);
    }
    if (start > l) {
      cmd[top].pos = l;
      cmd[top].a = k;
      cmd[top].b = k;
      cmd[top++].flag = 1;
      cmd[top].pos = start;
      cmd[top].a = start - l + k;
      cmd[top].b = k;
      cmd[top++].flag = -1;
    }
    if (maxk < k) maxk = k;
  }
  sort(cmd, cmd + top);
  int top1 = 0;
  for (int i = 0; i < top;) {
    int j = i + 1;
    while (j < top && cmd[j].pos == cmd[i].pos && cmd[j].a == cmd[i].a &&
           cmd[j].b == cmd[i].b && cmd[j].flag == cmd[i].flag)
      ++j;
    cmd[top1] = cmd[i];
    cmd[top1++].mul = j - i;
    i = j;
  }
  top = top1;
  for (int i = 1, j = 0; i <= n; ++i) {
    for (int x = maxk; x >= 1; --x) dp[x] = add(dp[x], dp[x - 1]);
    for (; j < top && cmd[j].pos == i; ++j) {
      if (cmd[j].flag > 0) {
        int pos = maxk - cmd[j].b;
        int curr = 1;
        int u = cmd[j].a;
        int v = 0;
        int cnt = cmd[j].mul;
        dp[pos] = add(dp[pos], mul(curr, cnt));
        while (pos + 1 <= maxk) {
          curr = mul(curr, u - v);
          curr = mul(curr, inv[v + 1]);
          ++v;
          ++pos;
          dp[pos] = add(dp[pos], mul(curr, cnt));
        }
      } else {
        int pos = maxk - cmd[j].b;
        int curr = 1;
        int u = cmd[j].a;
        int v = 0;
        int cnt = cmd[j].mul;
        dp[pos] = sub(dp[pos], mul(curr, cnt));
        while (pos + 1 <= maxk) {
          curr = mul(curr, u - v);
          curr = mul(curr, inv[v + 1]);
          ++v;
          ++pos;
          dp[pos] = sub(dp[pos], mul(curr, cnt));
        }
      }
    }
    data[i] = add(data[i], dp[maxk]);
  }
  for (int i = 1; i <= n; ++i) printf("%d ", data[i]);
  puts("");
  return 0;
}