Greg has an array a = a1, a2, ..., an and m operations. Each operation looks as: li, ri, di, (1 ≤ li ≤ ri ≤ n). To apply operation i to the array means to increase all array elements with numbers li, li + 1, ..., ri by value di.

Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m). That means that one should apply operations with numbers xi, xi + 1, ..., yi to the array.

Now Greg is wondering, what the array a will be after all the queries are executed. Help Greg.

Input

The first line contains integers n, m, k (1 ≤ n, m, k ≤ 105). The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105) — the initial array.

Next m lines contain operations, the operation number i is written as three integers: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).

Next k lines contain the queries, the query number i is written as two integers: xi, yi, (1 ≤ xi ≤ yi ≤ m).

The numbers in the lines are separated by single spaces.

Output

On a single line print n integers a1, a2, ..., an — the array after executing all the queries. Separate the printed numbers by spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.

Examples

Input

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3


Output

9 18 17


Input

1 1 1
1
1 1 1
1 1


Output

2


Input

4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3


Output

5 18 31 20
#include <bits/stdc++.h>
using namespace std;
class segtree {
 public:
  struct node {
    long long add = 0;
    long long sum = 0;
    void apply(int l, int r, long long v) {
      add += v;
      sum += v * (r - l);
    }
    friend ostream& operator<<(ostream& os, node& a) {
      os << "node(" << a.add << ", " << a.sum << ")";
      return os;
    }
  };
  node unite(const node& a, const node& b) {
    node res;
    res.sum = a.sum + b.sum;
    return res;
  }
  void push(int first, int l, int r) {
    int second = l + (r - l) / 2;
    if (tree[first].add != 0) {
      tree[first << 1].apply(l, second, tree[first].add);
      tree[first << 1 | 1].apply(second, r, tree[first].add);
      tree[first].add = 0;
    }
  }
  void pull(int first) {
    tree[first] = unite(tree[first << 1], tree[first << 1 | 1]);
  }
  int n;
  vector<node> tree;
  void build(int first, int l, int r) {
    if (l + 1 == r) {
      return;
    }
    int second = l + (r - l) / 2;
    build(first << 1, l, second);
    build(first << 1 | 1, second, r);
    pull(first);
  }
  template <typename M>
  void build(int first, int l, int r, const vector<M>& v) {
    if (l + 1 == r) {
      assert(0 <= l && l < (int)v.size());
      tree[first].apply(l, r, v[l]);
      return;
    }
    int second = l + (r - l) / 2;
    build(first << 1, l, second, v);
    build(first << 1 | 1, second, r, v);
    pull(first);
  }
  node get(int first, int l, int r, int lx, int rx) {
    if (rx <= l || r <= lx) {
      return node{};
    }
    if (lx <= l && r <= rx) {
      return tree[first];
    }
    push(first, l, r);
    int second = l + (r - l) / 2;
    node res = unite(get(first << 1, l, second, lx, rx),
                     get(first << 1 | 1, second, r, lx, rx));
    pull(first);
    return res;
  }
  template <typename... M>
  void modify(int first, int l, int r, int lx, int rx, const M&... v) {
    if (rx <= l || r <= lx) {
      return;
    }
    if (lx <= l && r <= rx) {
      tree[first].apply(l, r, v...);
      return;
    }
    int second = l + (r - l) / 2;
    push(first, l, r);
    if (lx < second) {
      modify(first << 1, l, second, lx, rx, v...);
    }
    if (rx > second) {
      modify(first << 1 | 1, second, r, lx, rx, v...);
    }
    pull(first);
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    int t = 1;
    while (t < n) {
      t <<= 1;
    }
    n = t;
    tree.resize(2 * n);
    build(1, 0, n);
  }
  template <typename M>
  segtree(const vector<M>& v) {
    n = v.size();
    int m = 1;
    while (m < n) {
      m <<= 1;
    }
    n = m;
    tree.resize(2 * n);
    vector<M> t = v;
    t.resize(n);
    build(1, 0, n, t);
  }
  node get(int lx, int rx) {
    assert(0 <= lx && lx <= rx && rx <= n);
    return get(1, 0, n, lx, rx);
  }
  node get(int p) {
    assert(0 <= p && p <= n);
    return get(1, 0, n, p, p + 1);
  }
  template <typename... M>
  void modify(int lx, int rx, const M&... v) {
    assert(0 <= lx && lx <= rx && rx <= n);
    modify(1, 0, n, lx, rx, v...);
  }
};
struct node {
  int first, second, d;
};
void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<long long> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  vector<node> op(m);
  for (int i = 0; i < m; i++) {
    int first, second, d;
    cin >> first >> second >> d;
    first--, second--;
    op[i] = {first, second, d};
  }
  segtree sg1(m);
  for (int i = 0; i < k; i++) {
    int first, second;
    cin >> first >> second;
    first--, second--;
    sg1.modify(first, second + 1, 1);
  }
  segtree sg2(v);
  for (int i = 0; i < m; i++) {
    int cnt = sg1.get(i, i + 1).sum;
    sg2.modify(op[i].first, op[i].second + 1, (long long)op[i].d * cnt);
  }
  for (int i = 0; i < n; i++) {
    cout << sg2.get(i, i + 1).sum << (i == n - 1 ? '\n' : ' ');
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}
