#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;
using vp = vector<pair<int, int>>;

#define rep(i, s, n) for (int i = s; i < (int)(n); i++)
#define sz(x) ((int)(x).size())
constexpr int INFI = 1001001001;
constexpr ll INFL = (1LL << 60);

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

	// input
	ll n, k, q;
	cin >> n >> k >> q;
	
	vl a (n);
	rep(i, 0, n){
		cin >> a[i];
	}
	sort (a.begin(), a.end());

	priority_queue<ll> A; // 降順
	priority_queue<ll, vector<ll>, greater<ll>> B; // 昇順
	rep (i, 0, k){ // K番目まで
		A.push(a[i]);
	}
	rep (i, k, n){ // K+1番目から
		B.push(a[i]);
	}
	
	rep (i, 0, q){
		int x;
		cin >> x;
		if(x == 1){ // yを追加する
			ll y;
			cin >> y;
			if(A.top() < y) B.push(y); // yがK番目より大きい→Bへ追加
			else{ // k番目より小さい
				ll a = A.top(); // K番目
				A.pop(); // AからK番目を削除
				A.push(y); // Aにyを追加(k番目になる)
				B.push(a); // Bに追加前のk番目を加える
			}
		}
		else if(x == 2){ // k番目にyを加えて追加する
			ll y;
			cin  >> y;
			ll z = A.top(); // k番目
			B.push(y + z); // k番目にyを加えてBに追加
			A.pop(); // k番目を削除
			A.push(B.top()); // Bの最少をAに追加(k番目になる)
			B.pop(); // Bの最少を削除
		}
		else{
			cout << A.top() << endl;
		}
	}

	return 0;
}