#include using namespace std; int main(){ int n, k, q; cin >> n >> k >> q; vector a(n); for(int i = 0; i < n; i++) cin >> a[i]; priority_queue pq1; priority_queue, greater<>> pq2; auto push = [&](long long x){ if((int) pq1.size() < k){ pq1.push(x); }else{ if(x < pq1.top()){ long long y = pq1.top(); pq1.pop(); pq1.push(x); pq2.push(y); }else{ pq2.push(x); } } }; for(int i = 0; i < n; i++) push(a[i]); while(q--){ int t; cin >> t; if(t == 1){ long long x; cin >> x; push(x); }else if(t == 2){ long long x; cin >> x; long long y = pq1.top(); pq1.pop(); if(!pq2.empty()){ pq1.push(pq2.top()); pq2.pop(); } push(y + x); }else{ cout << pq1.top() << endl; } } }