#include using namespace std; #define int long long signed main(){ int 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()); priority_queue small; priority_queue,greater> large; for(int i = 0; i < K; i++){ small.push(A[i]); } for(int i = K; i < N; i++){ large.push(A[i]); } large.push(1e18); for(int i = 0; i < Q; i++){ int q; cin>>q; if(q == 1){ int x; cin>>x; if(small.top() < x){ large.push(x); } else{ small.push(x); large.push(small.top()); small.pop(); } } if(q == 2){ int y; cin>>y; int now = small.top(); small.pop(); small.push(large.top()); large.pop(); now += y; if(small.top() < now){ large.push(now); } else{ small.push(now); large.push(small.top()); small.pop(); } } if(q == 3){ cout << small.top() << "\n"; } } }