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;
template <typename T>
T BigMod(T b, T p, T m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    T s = BigMod(b, p / 2, m);
    return ((s % m) * (s % m)) % m;
  }
  return ((b % m) * (BigMod(b, p - 1, m) % m)) % m;
}
template <typename T>
T ModInv(T b, T m) {
  return BigMod(b, m - 2, m);
}
template <typename T>
T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
template <typename T>
T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / gcd(a, b));
}
template <typename T>
T euclide(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
vector<string> split(const string &s, char d) {
  stringstream ss(s);
  string i;
  vector<string> e;
  while (getline(ss, i, d)) e.push_back(i);
  return e;
}
int Set(int n, int p) { return n | (1 << p); }
int Reset(int n, int p) { return n & ~(1 << p); }
bool Check(int n, int p) { return (bool)(n & (1 << p)); }
template <class T, class X>
inline T Toggle(T a, X i) {
  T t = 1;
  return (a ^ (t << i));
}
template <typename T, typename O>
void ForEach(T c, O o) {
  for_each(c.begin(), c.end(), o);
}
template <typename T, typename O>
T Map(T c, O o) {
  transform(c.begin(), c.end(), c.begin(), o);
  return c;
}
template <typename T, typename O>
T Zip(T fc, T sc, O o) {
  transform(fc.begin(), fc.end(), sc.begin(), fc.begin(), o);
  return fc;
}
template <typename T, typename N>
bool Exist(T c, N n) {
  return find_if(c.begin(), c.end(), n) != c.end();
}
template <typename T, typename P>
T FilterNot(T c, P p) {
  auto it = remove_if(c.begin(), c.end(), p);
  c.erase(it, end(c));
  return c;
}
template <typename T, typename P>
T Filter(T c, P p) {
  auto q = [p](typename T::value_type i) { return !p(i); };
  return FilterNot(c, q);
}
template <typename T>
T bit_read(T t[], T i) {
  T s = 0;
  while (i > 0) {
    s += t[i];
    i -= (i & -i);
  }
  return s;
}
template <typename T>
void bit_update(T t[], T i, T n, T v) {
  while (i <= n) {
    t[i] += v;
    i += (i & -i);
  }
}
template <typename T>
void bit_flatten(T t[], T n) {
  for (T i = 1; i <= n; i++) {
    t[i] += t[i - (i & -i)];
  }
}
template <typename T>
void bit_build(T t[], T n) {
  for (T i = 1; i <= n; i++) {
    t[i] -= t[i - (i & -i)];
  }
}
long long int bq[100007], bo[100007];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  long long int n, m, k;
  cin >> n >> m >> k;
  cin.ignore();
  vector<long long int> a;
  {
    string s;
    getline(cin, s);
    stringstream ss(s);
    copy(istream_iterator<long long int>(ss), istream_iterator<long long int>(),
         back_inserter(a));
  };
  vector<vector<long long int> >(op);
  for (int i = (0); i < (m); ++i) {
    vector<long long int> o;
    {
      string s;
      getline(cin, s);
      stringstream ss(s);
      copy(istream_iterator<long long int>(ss),
           istream_iterator<long long int>(), back_inserter(o));
    };
    op.push_back(o);
  }
  for (int i = (0); i < (k); ++i) {
    long long int x, y;
    cin >> x >> y;
    bit_update(bq, x, m, 1LL);
    bit_update(bq, y + 1, m, -1LL);
  }
  bit_flatten(bq, m);
  for (int i = (0); i < (m); ++i) {
    long long int l = op[i][0], r = op[i][1], d = op[i][2] * bq[i + 1];
    bit_update(bo, l, n, d);
    bit_update(bo, r + 1, n, -d);
  }
  bit_flatten(bo, n);
  for (int i = (0); i < (n); ++i) {
    cout << a[i] + bo[i + 1];
    cout << (i < n - 1 ? ' ' : '\n');
  }
  return 0;
}
