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;
long long tree[3 * 200000 + 2], arr[200000 + 2], lazy[3 * 200000 + 2];
long long counter[100001];
vector<int> v[100001];
long long midd(long long i, long long j) { return (i + j) / 2; }
long long lft(long long i) { return 2 * i + 1; }
long long ryt(long long i) { return 2 * i + 2; }
long long MAX_BUILD(long long head, long long i, long long j) {
  if (i == j) return tree[head] = arr[i];
  long long mid = midd(i, j);
  return tree[head] = max(MAX_BUILD(lft(head), i, mid),
                          MAX_BUILD(ryt(head), mid + 1, j));
}
void LAZY(long long head, long long i, long long j) {
  if (lazy[head]) {
    tree[head] += lazy[head];
    if (i != j) {
      lazy[lft(head)] += lazy[head];
      lazy[ryt(head)] += lazy[head];
    }
    lazy[head] = 0;
  }
  return;
}
void UPDATE(long long head, long long i, long long j, long long l, long long r,
            long long v) {
  LAZY(head, i, j);
  if (i > r || j < l) return;
  if (i >= l && j <= r) {
    tree[head] += v;
    if (i != j) {
      lazy[lft(head)] += v;
      lazy[ryt(head)] += v;
    }
    return;
  }
  long long mid = midd(i, j);
  UPDATE(lft(head), i, mid, l, r, v);
  UPDATE(ryt(head), mid + 1, j, l, r, v);
  tree[head] = max(tree[lft(head)], tree[ryt(head)]);
}
long long GET_MAX(long long head, long long i, long long j, long long l,
                  long long r) {
  if (j < l || i > r) return -INFINITY;
  LAZY(head, i, j);
  if (i >= l && j <= r) return tree[head];
  long long mid = midd(i, j);
  return max(GET_MAX(lft(head), i, mid, l, r),
             GET_MAX(ryt(head), mid + 1, j, l, r));
}
void print(long long head, long long i, long long j) {
  LAZY(head, i, j);
  if (i == j) {
    cout << tree[head] << " ";
    return;
  }
  long long mid = midd(i, j);
  print(lft(head), i, mid);
  print(ryt(head), mid + 1, j);
}
int main() {
  long long n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);
  MAX_BUILD(0, 0, n - 1);
  for (int i = 0; i < m; i++) {
    long long f, l, va;
    scanf("%lld%lld%lld", &f, &l, &va);
    f--;
    l--;
    v[i].push_back(f);
    v[i].push_back(l);
    v[i].push_back(va);
  }
  for (int i = 0; i < k; i++) {
    long long f, l;
    scanf("%lld%lld", &f, &l);
    f--;
    l--;
    counter[f]++;
    counter[l + 1]--;
  }
  for (int i = 0; i < m; i++) {
    if (i != 0) counter[i] += counter[i - 1];
    UPDATE(0, 0, n - 1, v[i][0], v[i][1], v[i][2] * counter[i]);
  }
  print(0, 0, n - 1);
  return 0;
}
