//#ifdef DEBUG
//#define _GLIBCXX_DEBUG
//#endif
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#else
#define debug(...) 228
#endif

#define pb push_back

typedef long long ll;
typedef long double ld;

const int BUF_SZ = 1 << 15;

inline namespace Input {
    char buf[BUF_SZ];
    int pos;
    int len;
    char next_char() {
        if (pos == len) {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, stdin);
            if (!len) { return EOF; }
        }
        return buf[pos++];
    }

    int read_int() {
        int x;
        char ch;
        int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }
        }
        x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
        return x * sgn;
    }
}  // namespace Input
inline namespace Output {
    char buf[BUF_SZ];
    int pos;

    void flush_out() {
        fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

    void write_char(char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;
    }

    void write_int(ll x) {
        static char num_buf[100];
        if (x < 0) {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
        write_char((char)('0' + x));
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');
    }

// auto-flush output when program exits
    void init_output() { assert(atexit(flush_out) == 0); }
}  // namespace Output

int n, m, z;
const int maxN = 1e6 + 10;
int tp[2 * maxN], p[2 * maxN], w[2 * maxN];
int a[maxN];
bool GEN = 0;
void read_input() {
//    cin >> n >> m >> z;
    mt19937 rnd(228);
    if (GEN) {
        n = 1000'000;
        m = 10'001;
        z = 999'999;
    }
    else {
//        cin >> n >> m >> z;
        n = read_int();
        m = read_int();
        z = read_int();
    }
    for (int i = 0; i < n; i++) {
//        cin >> a[i];
        if (GEN) {
            a[i] = rnd() % 1000'000 + 1;
        }
        else {
            a[i] = read_int();
//            cin >> a[i];
        }
    }
    int mm = m;
    int zz = z;
    for (int i = 0; i < m + z; i++) {
        if (GEN) {
            if ((rnd() % 2 && mm > 0) || (zz == 0)) {
                tp[i] = 1;
                p[i] = rnd() % n + 1;
                w[i] = rnd() % 1000'000 + 1;
                --mm;
            }
            else {
                tp[i] = 2;
                p[i] = rnd() % n + 1;
                w[i] = rnd() % 1000'000 + 1;
                --zz;
            }
        }
        else {
            tp[i] = read_int();
            p[i] = read_int();
            w[i] = read_int();
//            cin >> tp[i] >> p[i] >> w[i];
        }
        --p[i];
    }
    if (GEN) {
        assert(mm == 0 && zz == 0);
    }
}

//int msk[maxN];
//int id[maxN];
//int idR[maxN];
int SZ;
void compress() {
    vector<pair<int,int>> S;
    for (int i = 0; i < n; i++) {
        S.emplace_back(a[i], i);
    }
    int qqq = 0;
    for (int i = 0; i < m + z; i++) {
        if (tp[i] == 2) {
            S.emplace_back(w[i], ~i);
        }
    }
    sort(S.begin(), S.end());
    int prv_type = -1;
    int sz = -1;
    for (auto& it : S) {
        int our_type = (it.second < 0 ? 0 : 1);
        if ((our_type == 0 && prv_type == 1) || (prv_type == -1)) {
            sz++;
        }
        if (it.second < 0) {
            w[~it.second] = sz;
        }
        else {
            a[it.second] = sz;
        }
        prv_type = our_type;
    }
    SZ = sz + 2;
    assert(sz <= min(n, z) + 2);
//    for (int i = 0; i < n; i++) cout << a[i] << " ";
//    cout << endl;
//    for (int i = 0; i < m + z; i++) {
//        if (tp[i] == 2) cout << w[i] << " ";
//    }
//    cout << endl;
}

//int prep_cnt[maxS][maxS / B + 2];
//ll prep_sum[maxS / B + 2][B + 3];
//ll sum_block[maxS / B + 2];
//ll sum_solo[maxS];
//int sz_block[maxS / B + 2];
//int his_id[maxN];
//int id_in_block[maxS][maxS / B + 2];
void solve_small_n() {
    const int B = sqrt(n) + 1;
    const int cnt_blocks = (n + B - 1) / B;
    vector<vector<int>> prep_cnt(SZ + 1, vector<int>(cnt_blocks));
    vector<vector<int>> id_in_block(SZ + 1, vector<int>(cnt_blocks));
    vector<int> his_id(n);
    vector<int> sz_block(cnt_blocks);
    vector<vector<ll>> prep_sum(cnt_blocks, vector<ll>(B + 2));
    vector<ll> sum_solo(n);
    vector<ll> sum_block(cnt_blocks);
    for (int bl = 0; bl * B < n; bl++) {
        int L = bl * B;
        int R = min(L + B, n);
        for (int z = L; z < R; z++) {
            prep_cnt[a[z]][bl] += 1;
        }
        for (int z = SZ - 1; z >= 0; z--) {
            prep_cnt[z][bl] += prep_cnt[z + 1][bl];
        }
        vector<int> id(R - L);
        iota(id.begin(), id.end(), L);
        sort(id.begin(), id.end(), [&](int x, int y) {
            return a[x] < a[y];
        });
        int prv = -1;

        for (int x : id) {
            for (int c = prv + 1; c <= a[x]; c++) {
                id_in_block[c][bl] = sz_block[bl];
            }
            his_id[x] = sz_block[bl];
            sz_block[bl]++;
            prv = a[x];
        }
        for (int c = prv + 1; c <= SZ; c++) {
            id_in_block[c][bl] = sz_block[bl];
        }
        sz_block[bl]++;
    }
    for (int i = 0; i < m + z; i++) {
        if (tp[i] == 1) {
            int from = 0;
            int to = p[i] / B;
            for (int j = from; j < to; j++) {
                sum_block[j] += w[i];
            }
            for (int j = to * B; j <= p[i]; j++) {
                sum_solo[j] += w[i];
            }
            int L = to * B;
            int R = min(L + B, n);
            for (int j = 0; j <= sz_block[to]; j++) prep_sum[to][j] = 0;
            for (int j = L; j < R; j++) {
                prep_sum[to][his_id[j]] += sum_solo[j];
            }
            for (int j = sz_block[to] - 1; j >= 0; j--) prep_sum[to][j] += prep_sum[to][j + 1];
        }
        else {
            int from = 0;
            int to = p[i] / B;
            ll ans = 0;
            for (int j = from; j < to; j++) {
                ans += prep_sum[j][id_in_block[w[i]][j]] + prep_cnt[w[i]][j] * sum_block[j];
            }
            for (int j = to * B; j <= p[i]; j++) {
                if (a[j] >= w[i]) {
                    ans += sum_solo[j] + sum_block[to];
                }
            }
            write_int(ans);
        }
    }
}

int ask_L[2 * maxN];
int ask_R[2 * maxN];
int only_z_p[maxN];
int only_z_w[maxN];
ll ans[maxN];

int queries[maxN];
ll pref[maxN];
ll v[maxN];
ll D[maxN];

ll solo_add[maxN];
ll full[maxN];
ll solo[maxN];

int mmap[maxN];

int sz_z;
int tot_sz_z;
int sz_queries;

void process_block_smart() {
    for (int j = 0; j < sz_queries; j++) {
        ask_R[queries[j]] = tot_sz_z;
    }
    vector<int> inds(sz_z);
    iota(inds.begin(), inds.end(), tot_sz_z - sz_z);
    sort(inds.begin(), inds.end(), [&](int x, int y) {
        return only_z_p[x] < only_z_p[y];
    });
    memset(mmap, 0, (SZ + 2) * sizeof(int));
    for (int& v : inds) {
        mmap[only_z_w[v]] = 1;
    }
    mmap[0] = 1;
    int cur_sz = 0;
    for (int v = 0; v <= SZ; v++) {
        if (mmap[v]) {
            mmap[v] = cur_sz++;
        }
        else {
            mmap[v] = mmap[v - 1];
        }
    }
    //can be optimized to sqrt(z) by compressing once again, currently Z^2
    memset(D, 0, (cur_sz + 1) * sizeof(ll));
    for (int p = 0; p < (int)inds.size(); p++) {
        int c = inds[p];
        for (int L = ((p == 0) ? 0 : (only_z_p[inds[p - 1]] + 1)); L <= only_z_p[c]; L++) {
            D[mmap[a[L]]] += v[L];
        }
        for (int x = mmap[only_z_w[c]]; x <= cur_sz; x++) {
            ans[c] += D[x];
        }
    }
    sz_z = 0;
    //apply queries
    for (int j = 0; j < sz_queries; j++) {
        pref[0] += w[queries[j]];
        pref[p[queries[j]] + 1] -= w[queries[j]];
    }
    sz_queries = 0;
    for (int j = 0; j < n; j++) {
        pref[j + 1] += pref[j];
        v[j] += pref[j];
        pref[j] = 0;
    }
}


ll fenw[maxN];
int FOR_FEN = 0;
void upd(int v, ll by) {
    v = FOR_FEN - v;
    while (v <= FOR_FEN) {
        fenw[v] += by;
        v = (v | (v - 1)) + 1;
    }
}
ll get(int r) {
    r = FOR_FEN - r;
    ll ans = 0;
    while (r > 0) {
        ans += fenw[r];
        r &= (r - 1);
    }
    return ans;
}

void process_block_fenw() {
    for (int j = 0; j < sz_queries; j++) {
        ask_R[queries[j]] = tot_sz_z;
    }

    //answer for current queries
    vector<int> inds(sz_z);
    iota(inds.begin(), inds.end(), tot_sz_z - sz_z);
    sort(inds.begin(), inds.end(), [&](int x, int y) {
        return only_z_p[x] < only_z_p[y];
    });
    //can be optimized to sqrt(z) by compressing once again, currently Z^2
//        memset(D, 0, sizeof D);
    for (int p = 0; p <= FOR_FEN; p++) {
        fenw[p] = 0;
    }
    for (int p = 0; p < (int)inds.size(); p++) {
        int c = inds[p];
        for (int L = ((p == 0) ? 0 : (only_z_p[inds[p - 1]] + 1)); L <= only_z_p[c]; L++) {
            upd(a[L], v[L]);
        }
        ans[c] += get(only_z_w[c]);
    }
    sz_z = 0;
    //apply queries
    for (int j = 0; j < sz_queries; j++) {
        pref[0] += w[queries[j]];
        pref[p[queries[j]] + 1] -= w[queries[j]];
    }
    sz_queries = 0;
    for (int j = 0; j < n; j++) {
        pref[j + 1] += pref[j];
        v[j] += pref[j];
        pref[j] = 0;
    }
}

ll tot_pairs = 0;
void rebuild() {
    ll estimate_fenw = n * 100 + sz_z * 100;
    ll estimate_smart = 1LL * sz_z * sz_z + n;
    if (estimate_smart <= estimate_fenw) {
        process_block_smart();
    }
    else {
        process_block_fenw();
    }
    tot_pairs = 0;
}

void finish_smart() {
    vector<pair<int,int>> ques;
    ques.reserve(m + z);
    for (int i = 0; i < m + z; i++) {
        if (tp[i] == 1) {
            for (int x = ask_L[i]; x < ask_R[i]; x++) {
                if (only_z_p[x] <= p[i]) {
                    solo_add[x] += w[i];
                }
            }
            ques.emplace_back(p[i], i);
        }
    }
    for (int i = 0; i < z; i++) {
        ques.emplace_back(only_z_p[i], ~i);
    }
    sort(ques.begin(), ques.end());
    const int B = sqrt(SZ + 1) + 1;
    for (int i = 0; i < ques.size(); i++) {
        for (int x = (i == 0 ? 0 : ques[i - 1].first + 1); x <= ques[i].first; x++) {
            //upd a[x]
            int from = 0;
            int to = a[x] / B;
            for (int c = from; c < to; c++) {
                full[c] += 1;
            }
            for (int c = to * B; c <= a[x]; c++) {
                solo[c] += 1;
            }
        }
        int id = ques[i].second;
        if (id < 0) {
            id = ~id;
            ans[id] += (full[only_z_w[id] / B] + solo[only_z_w[id]]) * solo_add[id];
        }
        else {
            for (int x = ask_L[id]; x < ask_R[id]; x++) {
                if (only_z_p[x] > p[id]) {
                    ans[x] += (full[only_z_w[x] / B] + solo[only_z_w[x]]) * w[id];
                }
            }
        }
    }
    for (int i = 0; i < z; i++) {
        cout << ans[i] << '\n';
    }
}

void finish_fenwick() {
    vector<pair<int,int>> ques;
    ques.reserve(m + z);
    for (int i = 0; i < m + z; i++) {
        if (tp[i] == 1) {
            for (int x = ask_L[i]; x < ask_R[i]; x++) {
                if (only_z_p[x] <= p[i]) {
                    solo_add[x] += w[i];
                }
            }
            ques.emplace_back(p[i], i);
        }
    }
    for (int i = 0; i < z; i++) {
        ques.emplace_back(only_z_p[i], ~i);
    }
    sort(ques.begin(), ques.end());
    memset(fenw, 0, sizeof fenw);
    for (int i = 0; i < (int)ques.size(); i++) {
        for (int x = (i == 0 ? 0 : ques[i - 1].first + 1); x <= ques[i].first; x++) {
            upd(a[x], 1);
        }
        int id = ques[i].second;
        if (id < 0) {
            id = ~id;
            ans[id] += get(only_z_w[id]) * solo_add[id];
        }
        else {
            for (int x = ask_L[id]; x < ask_R[id]; x++) {
                if (only_z_p[x] > p[id]) {
                    ans[x] += get(only_z_w[x]) * w[id];
                }
            }
        }
    }
    for (int i = 0; i < z; i++) {
        cout << ans[i] << '\n';
    }
}

void finish() {
    ll upds = n;
    ll ask = 0;
    for (int i = 0; i < m + z; i++) {
        if (tp[i] == 1) {
            ask += ask_R[i] - ask_L[i];
        }
    }
    const int B = sqrt(SZ + 1);
    if (((ask + upds * B <= upds * 75 + ask * 75)  || z <= 10'000)) {
        finish_smart();
    }
    else {
        finish_fenwick();
    }
}

void solve_small_mz() {
    FOR_FEN = SZ + 1;
    const int est = (int)sqrt(z);
    const int est2 = (int)sqrt(1LL * m * z);
    for (int i = 0; i < m + z; i++) {
        if (tp[i] == 1) {
            if (m == 10'000 && sz_queries >= 102) {
                rebuild();
                assert(sz_z == 0 && sz_queries == 0);
            }
            ask_L[i] = tot_sz_z;
            ask_R[i] = tot_sz_z;
            queries[sz_queries++] = i;
        }
        else {
            tot_pairs += sz_queries;
            if ((z == 10'000 && sz_z >= 102) || (z != 10'000 && sz_z >= 5 * est) || (z != 10'000 && tot_pairs >= 4 * est2)) {
                rebuild();
                assert(sz_z == 0 && sz_queries == 0);
            }
            only_z_p[tot_sz_z] = p[i];
            only_z_w[tot_sz_z] = w[i];
            tot_sz_z++;
            sz_z++;
        }
    }
    if (sz_z) {
        rebuild();
    }
    finish();
}


int main() {
    init_output();
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
    auto start = std::chrono::high_resolution_clock::now();
#ifdef DEBUG
    freopen("2.in", "r", stdin);
#endif
    read_input();
    compress();
    if (n == 10'000) solve_small_n();
    else if ((m == 10'000) || (z == 10'000)) solve_small_mz();
    else {
        if (n <= 350'000) solve_small_n();
        else solve_small_mz();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cerr << "Execution Time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
              << " ms" << std::endl;
    return 0;
}