#include using namespace std; using lint = long long; int main() { lint n, k, q; cin >> n >> k >> q; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end()); multiset l, r; for (int i = 0; i < k; i++) l.insert(a[i]); for (int i = k; i < n; i++) r.insert(a[i]); for (int qu = 0; qu < q; qu++) { int t; cin >> t; if (t == 1) { lint x; cin >> x; l.insert(x); r.insert(*l.rbegin()); l.erase(l.find(*l.rbegin())); } else if (t == 2) { lint y; cin >> y; lint high = *l.rbegin(); l.erase(l.find(high)); if (r.empty() || *r.begin() > high+y) l.insert(high+y); else { r.insert(high+y); l.insert(*r.begin()); r.erase(r.find(*r.begin())); } } else if (t == 3) { cout << *l.rbegin() << endl; } } }