#include #include #define chmin(x,y) (x) = min((x),(y)) #define chmax(x,y) (x) = max((x),(y)) #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define vec vector #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define pb push_back #define eb emplace_back using namespace std; using namespace atcoder; using ll = long long; using ld = long double; const ll mod = 998244353; using mint = modint998244353; const vector dx = {1,0,-1,0}, dy = {0,1,0,-1}; // using Graph = vector>>; using Graph = vector>; int main(){ // input int N,K,Q; cin >> N >> K >> Q; priority_queue pq; priority_queue,greater> qq; vector A(N); rep(i,N) cin >> A[i]; sort(all(A)); rep(i,N){ if(i < K) pq.push(A[i]); else qq.push(A[i]); } assert(pq.size() == K); assert(qq.size() == N-K); // solve while(Q--){ int q; cin >> q; if(q == 3) cout << pq.top() << "\n"; else if(K == N){ ll x; cin >> x; if(q == 1) pq.push(x); else{ x += pq.top(); pq.pop(); pq.push(x); } } else if(q == 1){ ll x; cin >> x; if(x >= pq.top()) qq.push(x); else{ pq.push(x); qq.push(pq.top()); pq.pop(); } } else if(q == 2){ ll y; cin >> y; y += pq.top(); pq.pop(); if(y <= qq.top()) pq.push(y); else{ qq.push(y); pq.push(qq.top()); qq.pop(); } } if(K < N) assert(pq.top() <= qq.top()); } // output }