#include <bits/stdc++.h>

using ll = long long;

using namespace std;
 
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE], *BB, *BE;
char gc() {
  return BB == BE ? (BE = (BB = BUFF) + fread(BUFF, 1, BUFF_SIZE, stdin), BB == BE ? EOF : *BB++) : *BB++;
}
void read() {}
template<class T, class ...Ts>
void read(T &x, Ts &...args) {
  x = 0;
  char ch = 0, w = 0;
  while (ch < '0' || ch > '9')
    w |= ch == '-', ch = gc();
  while (ch >= '0' && ch <= '9')
    x = x * 10 + (ch ^ '0'), ch = gc();
  if (w) x = -x;
  read(args...);
}

const int mod = 1004535809;
int norm(int x) { return x >= mod ? x - mod : x; }
int reduce(int x) { return x < 0 ? x + mod : x; }
int neg(int x) { return x ? mod - x : 0; }
void add(int &x, int y) { if ((x += y - mod) < 0) x += mod; }
void sub(int &x, int y) { if ((x -= y) < 0) x += mod; }
void fam(int &x, int y, int z) { x = (x + (ll)y * z) % mod; }
int mpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1) {
    if (b & 1) ret = (ll)ret * a % mod;
    a = (ll)a * a % mod;
  }
  return ret;
}

const int BRUTE_N2_LIMIT = 50;

namespace NTT {
  int L = -1;
  vector<int> root;
  void init(int l) {
    L = l;
    root.resize((1 << L) + 1);
    int n = 1 << L, *w = root.data();
    w[0] = 1, w[1 << L] = mpow(4172, 1 << (19 - L));
    for (int i = L; i; --i) w[1 << (i - 1)] = (ll)w[1 << i] * w[1 << i] % mod;
    for (int i = 1; i < n; ++i) w[i] = (ll)w[i & (i - 1)] * w[i & -i] % mod;
  }
  void DIF(int *a, int l) {
    int n = 1 << l;
    for (int len = n >> 1; len; len >>= 1)
      for (int *j = a, *o = root.data(); j != a + n; j += len << 1, ++o)
        for (int *k = j; k != j + len; ++k) {
          int r = (ll)*o * k[len] % mod;
          k[len] = reduce(*k - r), add(*k, r);
        }
  }
  void DIT(int *a, int l) {
    int n = 1 << l;
    for (int len = 1; len < n; len <<= 1)
      for (int *j = a, *o = root.data(); j != a + n; j += len << 1, ++o)
        for (int *k = j; k != j + len; ++k) {
          int r = norm(*k + k[len]);
          k[len] = (ll)*o * (*k - k[len] + mod) % mod, *k = r;
        }
  }
  void fft(int *a, int lgn, int d = 1) {
    if (L < lgn) init(lgn);
    int n = 1 << lgn;
    if (d == 1) DIF(a, lgn);
    else {
      DIT(a, lgn), reverse(a + 1, a + n);
      int nInv = mod - (mod - 1) / n;
      for (int i = 0; i < n; ++i) a[i] = (ll)a[i] * nInv % mod;
    }
  }
}

struct poly {
  vector<int> a;
  poly(ll v = 0): a(1) {
    if ((v %= mod) < 0) v += mod;
    a[0] = v;
  }
  poly(const poly &o): a(o.a) {}
  poly(const vector<int> &o): a(o) {}
  poly(initializer_list<int> o): a(o) {}
  int operator[](int k) const { return k < a.size() ? a[k] : 0; }
  int &operator[](int k) {
    if (k >= a.size()) a.resize(k + 1);
    return a[k];
  }
  int deg() const { return (int)a.size() - 1; }
  void redeg(int d) { a.resize(d + 1); }
  int size() const { return a.size(); }
  void resize(int s) { a.resize(s); }
  poly slice(int d) const {
    if (d < a.size()) return vector<int>(a.begin(), a.begin() + d + 1);
    vector<int> ret = a;
    ret.resize(d + 1);
    return ret;
  }
  poly shift(int k) const {
    if (size() + k <= 0) return 0;
    vector<int> ret(size() + k);
    for (int i = max(0, k); i < ret.size(); ++i) ret[i] = a[i - k];
    return ret;
  }
  int *base() { return a.data(); }
  const int *base() const { return a.data(); }
  poly operator*(const poly &) const;
  poly &operator*=(const poly &o) {
    *this = operator*(o);
    return *this;
  }
};

poly zeroes(int d) { return vector<int>(d + 1); }

namespace NTT {
  void fft(poly &a, int lgn, int d = 1) { fft(a.base(), lgn, d); }
}

using NTT::fft;

poly poly::operator*(const poly &o) const {
  int n = deg(), m = o.deg();
  if (n <= 10 || m <= 10 || n + m <= BRUTE_N2_LIMIT) {
    poly ret = zeroes(n + m);
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= m; ++j) fam(ret[i + j], a[i], o[j]);
    return ret;
  }
  n += m;
  int l = 0;
  while ((1 << l) <= n) ++l;
  poly ret = a, tmp = o;
  ret.resize(1 << l), tmp.resize(1 << l);
  fft(ret, l), fft(tmp, l);
  for (int i = 0; i < (1 << l); ++i) ret[i] = (ll)ret[i] * tmp[i] % mod;
  fft(ret, l, -1);
  return ret.slice(n);
}

const int N = 1e5;
const int W = 10;

int n, m, a[N + 5];
vector<vector<int>> upd;
int res[N + 5];

int main() {
  read(n);
  for (int i = 0; i < n; ++i) read(a[i]);
  upd.resize(((n - 1) >> W) + 1);
  for (read(m); m; --m) {
    int l, r, s; read(l, r, s), --l, --r, --s;
    int L = l >> W, R = r >> W;
    if (L == R)
      for (int j = l; j <= r; ++j) res[s + j - l] += a[j];
    else {
      for (int j = l; j < ((L + 1) << W); ++j) res[s + j - l] += a[j];
      for (int j = R << W; j <= r; ++j) res[s + j - l] += a[j];
      if (L + 1 < R) upd[L + 1].push_back(s + ((L + 1) << W) - l), upd[R].push_back(-(s + (R << W) - l));
    }
  }
  poly f = zeroes(n - 1);
  for (int p = 0; p <= ((n - 1) >> W); ++p) {
    int l = p << W, r = min((p + 1) << W, n);
    for (int i = n - 1; i >= (1 << W); --i) f[i] = f[i - (1 << W)];
    fill(f.base(), f.base() + (1 << W), 0);
    for (int i: upd[p]) 
      if (i > 0) ++f[i];
      else --f[-i];
    poly g = zeroes(r - l - 1);
    copy(a + l, a + r, g.base());
    g *= f;
    for (int i = 0; i < n; ++i) res[i] += g[i];
  }
  for (int i = 0; i < n; ++i) printf("%d\n", res[i]);
}