#include using namespace std; using ll = long long; using ull = unsigned long long; const int INF = 2e9; const ll LINF = 2e18; #define rep(i, n) for (int i = 0; (i) < (n); (i)++) #define rep1(i, n) for (int i = 1; (i) < ((n) + 1); (i)++) #define all(a) (a).begin(), (a).end() const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; int main(){ ll N,K,Q; cin>>N>>K>>Q; vector A(N); priority_queue, less> P1; priority_queue, greater> P2; rep(i,N){ cin>>A[i]; } sort(all(A)); rep(i,N){ if(i < K){ P1.push(A[i]); } else { P2.push(A[i]); } } while(Q--){ int q; cin>>q; if(q==1){ ll x; cin>>x; if(P1.top() > x){ auto t = P1.top(); P1.pop(); P1.push(x); P2.push(t); } else { P2.push(x); } } else if(q==2){ ll y; cin>>y; auto t = P1.top(); if(P2.empty() || t+y <= P2.top()){ P1.pop(); P1.push(t+y); } else { auto u = P2.top(); P1.pop(); P2.pop(); P1.push(u); P2.push(t+y); } } else { cout<