#include using namespace std; using ll = long long; int main () { int N, K, Q; cin >> N >>K >> Q; priority_queue pque1; priority_queue, greater> pque2; auto add = [&](ll x) -> void { pque1.push(x); if (pque1.size() > K) { pque2.push(pque1.top()); pque1.pop(); } }; auto ers = [&]() -> ll { ll ret = pque1.top(); pque1.pop(); if (!pque2.empty()) { pque1.push(pque2.top()); pque2.pop(); } }; while (N--) { ll a; cin >> a; add(a); } while (Q--) { int t; cin >> t; if (t == 1) { ll x; cin >> x; add(x); } else if (t == 2) { ll y; cin >> y; y += ers(); add(y); } else { cout << pque1.top() << endl; } } }