// GPT-o4-mini-highによる生成コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Event {
    int R, pos;
    ll delta;
};

struct Query {
    int idx;
    int R, D, U;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    cin >> N >> K >> Q;

    vector<ll> B(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> B[i];
    }
    // Prefix sums of B
    vector<ll> P(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        P[i] = P[i - 1] + B[i];
    }

    vector<int> p(K + 1);
    vector<ll> X(K + 1);
    for (int k = 1; k <= K; k++) {
        cin >> p[k] >> X[k];
    }

    // Compute d[k] = X[k] - B[p[k]]; only keep if positive
    vector<ll> d(K + 1, 0);
    vector<vector<pair<int,ll>>> updList(N + 1);
    for (int k = 1; k <= K; k++) {
        ll diff = X[k] - B[p[k]];
        if (diff > 0) {
            d[k] = diff;
            updList[p[k]].push_back({k, diff});
        }
    }

    // For each position, compute prev/next greater among its updates
    // We'll collect primitive events: at certain L, (R,pos,delta)
    vector<vector<Event>> event_list(K + 2); // L from 1..K+1

    for (int i = 1; i <= N; i++) {
        auto &vec = updList[i];
        int m = (int)vec.size();
        if (m == 0) continue;
        vector<int> times(m);
        vector<ll> vals(m);
        for (int j = 0; j < m; j++) {
            times[j] = vec[j].first;
            vals[j] = vec[j].second;
        }
        vector<int> prev_greater(m, -1), next_greater(m, m);
        // prev greater: nearest j' < j with vals[j'] > vals[j]
        {
            vector<int> st;
            for (int j = 0; j < m; j++) {
                while (!st.empty() && vals[st.back()] <= vals[j]) {
                    st.pop_back();
                }
                if (!st.empty()) prev_greater[j] = st.back();
                else prev_greater[j] = -1;
                st.push_back(j);
            }
        }
        // next greater: nearest j' > j with (vals[j'] > vals[j]) OR (vals[j'] == vals[j])
        // i.e., nearest with vals[j'] >= vals[j]
        {
            vector<int> st;
            for (int j = m - 1; j >= 0; j--) {
                while (!st.empty() && vals[st.back()] < vals[j]) {
                    st.pop_back();
                }
                if (!st.empty()) next_greater[j] = st.back();
                else next_greater[j] = m;
                st.push_back(j);
            }
        }
        // For each j, compute L_low, L_high, R_low, R_high, generate events
        for (int j = 0; j < m; j++) {
            int T_j = times[j];
            int T_prev = (prev_greater[j] == -1 ? 0 : times[prev_greater[j]]);
            int T_next = (next_greater[j] == m ? K + 1 : times[next_greater[j]]);
            int L_low = T_prev + 1;
            int L_high = T_j;
            int R_low = T_j;
            int R_high = T_next - 1;
            ll delta = vals[j];
            // At L = L_low: add +delta on [R_low, R_high] at pos=i
            // At L = L_high+1: add -delta on [R_low, R_high] at pos=i
            // Decompose range update on R into two point updates: at R_low: +delta; at R_high+1: -delta
            // Activation at L_low:
            if (L_low <= K) {
                // +delta at R_low
                event_list[L_low].push_back({R_low, i, +delta});
                // -delta at R_high+1 (i.e., at R = R_high+1)
                if (R_high + 1 <= K + 1) {
                    event_list[L_low].push_back({R_high + 1, i, -delta});
                }
            }
            // Deactivation at L_high + 1:
            int L_off = L_high + 1;
            if (L_off <= K + 1) {
                // -delta at R_low
                event_list[L_off].push_back({R_low, i, -delta});
                // +delta at R_high+1
                if (R_high + 1 <= K + 1) {
                    event_list[L_off].push_back({R_high + 1, i, +delta});
                }
            }
        }
    }

    // Read queries, group by L_q
    vector<vector<Query>> query_list(K + 2);
    vector<ll> ans_extra(Q, 0);
    vector<int> qL(Q), qR(Q), qD(Q), qU(Q);
    for (int j = 0; j < Q; j++) {
        int Lq, Rq, Dq, Uq;
        cin >> Lq >> Rq >> Dq >> Uq;
        qL[j] = Lq;
        qR[j] = Rq;
        qD[j] = Dq;
        qU[j] = Uq;
        if (Lq <= K) {
            query_list[Lq].push_back({j, Rq, Dq, Uq});
        }
    }

    // Build BIT-of-BIT structure over R in [1..K+1], pos in [1..N]
    int Rmax = K + 1;
    vector<vector<int>> BIT_nodes(Rmax + 1);
    // Collect all (R,pos) from primitive events
    for (int L = 1; L <= K + 1; L++) {
        for (auto &e : event_list[L]) {
            int R = e.R;
            int pos = e.pos;
            for (int i = R; i <= Rmax; i += (i & -i)) {
                BIT_nodes[i].push_back(pos);
            }
        }
    }
    // Also, for queries, we need to query pos up to qU and qD-1; no need to add pos here,
    // as BIT_nodes only stores pos that appear in updates.

    // Sort & deduplicate BIT_nodes, and create BIT_vals
    vector<vector<ll>> BIT_vals(Rmax + 1);
    for (int i = 1; i <= Rmax; i++) {
        auto &vec = BIT_nodes[i];
        if (!vec.empty()) {
            sort(vec.begin(), vec.end());
            vec.erase(unique(vec.begin(), vec.end()), vec.end());
            BIT_vals[i].assign(vec.size() + 1, 0LL);
        }
    }

    // BIT-of-BIT update: add delta at (R,pos)
    auto bit_update = [&](int R, int pos, ll delta) {
        for (int i = R; i <= Rmax; i += (i & -i)) {
            auto &nodes = BIT_nodes[i];
            if (nodes.empty()) continue;
            int idx = int(lower_bound(nodes.begin(), nodes.end(), pos) - nodes.begin()) + 1;
            auto &vals = BIT_vals[i];
            int sz = (int)nodes.size();
            for (int t = idx; t <= sz; t += (t & -t)) {
                vals[t] += delta;
            }
        }
    };

    // BIT-of-BIT query: sum of values for R' ≤ R_q and pos' ≤ x
    auto bit_query = [&](int R, int x) {
        ll res = 0;
        for (int i = R; i > 0; i -= (i & -i)) {
            auto &nodes = BIT_nodes[i];
            if (nodes.empty()) continue;
            int idx = int(upper_bound(nodes.begin(), nodes.end(), x) - nodes.begin());
            if (idx <= 0) continue;
            auto &vals = BIT_vals[i];
            for (int t = idx; t > 0; t -= (t & -t)) {
                res += vals[t];
            }
        }
        return res;
    };

    // Sweep L from 1 to K+1
    for (int L = 1; L <= K + 1; L++) {
        // Process all primitive events at this L
        for (auto &e : event_list[L]) {
            int R = e.R;
            int pos = e.pos;
            ll delta = e.delta;
            if (R >= 1 && R <= Rmax) {
                bit_update(R, pos, delta);
            }
        }
        // Process queries with L_q = L
        if (L <= K) {
            for (auto &q : query_list[L]) {
                int j = q.idx;
                int Rq = q.R;
                int Dq = q.D;
                int Uq = q.U;
                if (Rq > Rmax) Rq = Rmax;
                ll sumU = bit_query(Rq, Uq);
                ll sumD_1 = bit_query(Rq, Dq - 1);
                ans_extra[j] = sumU - sumD_1;
            }
        }
    }

    // Compute final answers
    vector<ll> ans(Q, 0);
    for (int j = 0; j < Q; j++) {
        ll base = P[qU[j]] - P[qD[j] - 1];
        ans[j] = base + ans_extra[j];
    }

    // Output
    ostringstream oss;
    for (int j = 0; j < Q; j++) {
        oss << ans[j] << '\n';
    }
    cout << oss.str();

    return 0;
}