#include using namespace std; int main() { int N, K, Q; cin >> N >> K >> Q; priority_queue APQ; priority_queue, greater> BPQ; for (int i = 0; i < N; i++) { int A; cin >> A; APQ.push(A); if ((int)APQ.size() >= K) { BPQ.push(APQ.top()); APQ.pop(); } } for (int i = 0; i < Q; i++) { int type; cin >> type; if (type == 1) { int x; cin >> x; if (x > APQ.top()) BPQ.push(x); else { APQ.push(x); BPQ.push(APQ.top()); APQ.pop(); } } if (type == 2) { int y; cin >> y; long long t = BPQ.top() + y; BPQ.pop(); BPQ.push(t); } if (type == 3) cout << BPQ.top() << endl; } }