#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];

int k;
int main() {
    cin >> n >> k >> m;
    for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
    sort(w + 1, w + n + 1);
    priority_queue<ll, vector<ll>, less<ll> > q1;
    priority_queue<ll, vector<ll>, greater<ll> > q2;
    for (int i = 1; i < k + 1; i++) q1.push(w[i]);
    for (int i = k + 1; i < n + 1; i++) q2.push(w[i]);
    while (m--) {
        int op, x;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d", &x);
            if (x < q1.top()) {
                q2.push(q1.top()), q1.pop();
                q1.push(x);
            } else q2.push(x);
        } else if (op == 2) {
            scanf("%d", &x);
            ll u = q1.top() + x, v = q2.top(); q1.pop(), q2.pop();
            q1.push(min(u, v)), q2.push(max(u, v));
        } else printf("%lld\n", q1.top());
    }
    return 0;
}