#include using namespace std; struct SplitMultiset2{ //上位(下位)K個とそれ以外に分ける. //削除クエリがないならpriorityqueueで簡潔&定数倍改善. private: int siz,K; bool Max; multiset L,R; long long val,ex; //val->min(siz,K)個の和,ex->範囲外の和,Max->大きい方が偉い?; //L->K個採用集合,R->不採用集合. //構築O(|A|log|A|),クエリO(logsiz). public: template SplitMultiset2(int k,bool M,vector A){ K = k; siz = A.size(); Max = M; val = 0; ex = 0; sort(A.begin(),A.end()); long long inf = numeric_limits::max(); if(Max){ if(siz <= K){ L = multiset(A.begin(),A.end()); for(auto &a : A) val += a; } else{ L = multiset(A.begin()+siz-K,A.end()); R = multiset(A.begin(),A.begin()+siz-K); for(int i=0; i(A.begin(),A.end()); for(auto &a : A) val += a; } else{ L = multiset(A.begin(),A.begin()+K); R = multiset(A.begin()+K,A.end()); for(int i=0; i::max(); if(Max) L = {inf},R = {-inf}; else L = {-inf},R = {inf}; } void add(long long x){ //xを追加する siz++; if(siz <= K){ //K個以下なら採用. val += x; L.insert(x); return; } if((Max && *L.begin() >= x)||(!Max && *L.rbegin() <= x)){ ex += x; R.insert(x); return; } val += x; L.insert(x); if(Max){ long long v = *L.begin(); ex += v; val -= v; R.insert(v); L.erase(L.begin()); } else{ long long v = *L.rbegin(); ex += v; val -= v; R.insert(v); L.erase(--L.end()); } } void erase(long long x){ //xを削除する xは存在しなければならない. siz--; if(siz < K){ //K個以下なら絶対消える. val -= x; L.erase(L.find(x)); return; } auto itr = R.find(x); if(itr != R.end()){ ex -= x; R.erase(itr); return; } itr = L.find(x); assert(itr != L.end()); val -= x; L.erase(itr); if(Max){ long long v = *R.rbegin(); val += v; ex -= v; L.insert(v); R.erase(--R.end()); } else{ long long v = *R.begin(); val += v; ex -= v; L.insert(v); R.erase(R.begin()); } } long long Kth(){ //K番目を返す. assert(siz >= K); if(Max) return *L.begin(); else return *L.rbegin(); } long long sum(){return val;} //採用の和を返す. long long qwerty(){return ex;} //不採用の和 要る?これ 雑魚命名してます. int size(){return siz;} //要素数を返す. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,K,Q; cin >> N >> K >> Q; vector A(N); for(auto &a : A) cin >> a; SplitMultiset2 Z(K,false,A); while(Q--){ int t; cin >> t; if(t == 3) cout << Z.Kth() << "\n"; else if(t == 1){ int x; cin >> x; Z.add(x); } else{ long long y; cin >> y; long long v = Z.Kth(); Z.erase(v),Z.add(v+y); } } }