Greg has an array *a* = *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> and *m* operations. Each operation looks as: *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>, (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*). To apply operation *i* to the array means to increase all array elements with numbers *l*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub> + 1, ..., *r*<sub class="lower-index">*i*</sub> by value *d*<sub class="lower-index">*i*</sub>.

Greg wrote down *k* queries on a piece of paper. Each query has the following form: *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>, (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *y*<sub class="lower-index">*i*</sub> ≤ *m*). That means that one should apply operations with numbers *x*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i*</sub> + 1, ..., *y*<sub class="lower-index">*i*</sub> to the array.

Now Greg is wondering, what the array *a* will be after all the queries are executed. Help Greg.
The first line contains integers *n*, *m*, *k* (1 ≤ *n*, *m*, *k* ≤ 10<sup class="upper-index">5</sup>). The second line contains *n* integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>) — the initial array.

Next *m* lines contain operations, the operation number *i* is written as three integers: *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>, (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*), (0 ≤ *d*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>).

Next *k* lines contain the queries, the query number *i* is written as two integers: *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>, (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *y*<sub class="lower-index">*i*</sub> ≤ *m*).

The numbers in the lines are separated by single spaces.
#include <bits/stdc++.h>


using namespace std;

typedef long double ld;
typedef int64_t ll;

struct Operation {
    int l, r, d;
};

vector<int> pref(vector<int> v) {
    vector<int> s(v.size());
    s[0] = 0;
    for (size_t i = 0; i < s.size() - 1; ++i) {
        s[i + 1] = s[i] + v[i];
    }
    s.erase(s.begin());
    return s;
}

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<int> v(n);
    vector<Operation> oper(m);
    for (ll i = 0; i < n; ++i) {
        cin >> v[i];
    }
    for (ll i = 0; i < m; ++i) {
        Operation o;
        cin >> o.l >> o.r >> o.d;
        oper[i] = o;
    }
    for (ll i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        vector<int> tmp(n + 1, 0);
        for (int i = x - 1; i < y; ++i) {
            Operation cur = oper[i];
            tmp[cur.l - 1] += cur.d;
            tmp[cur.r] += -cur.d;
        }
        tmp = pref(tmp);
        for (int i = 0; i < n; ++i) {
            v[i] += tmp[i];
        }
    }

    for (auto i : v) {
        cout << i << " ";
    }


    return 0;
}
