#include using namespace std; #define ALL(x) (x).begin(), (x).end() #define REP(i,n) for(int i=0; ib ? a=b, true : false; } using ll=long long; const int INF=1e9+10; const ll INFL=4e18; #ifdef DEBUG #include "./debug.hpp" #else #define debug(...) #define print_line #endif #include #include using namespace __gnu_pbds; template struct SortedMultiTree:tree,null_type,less>,rb_tree_tag,tree_order_statistics_node_update> { using tree,null_type,less>,rb_tree_tag,tree_order_statistics_node_update>::tree; using P=pair; T not_found=-1; SortedMultiTree()=default; /// @brief コンストラクタ /// @param not_found 指定の値が見つからなかったときに返す値 SortedMultiTree(T not_found=-1) { this->not_found=not_found; } /// @brief x を追加する void add(T x) { if(this->size()==0) { this->insert(P{x,0}); return; } auto itr=this->lower_bound(P{x+1,0}); if(itr==this->begin()) { this->insert(P{x,0}); return; } itr--; if(itr->first!=x) { this->insert(P{x,0}); return; } this->insert(P{x,itr->second+1}); } /// @brief 最小値を返す T min() { if(this->empty())return not_found; return*this->begin()->first; } /// @brief 最大値を返す T max() { if(this->empty())return not_found; return*this->rbegin()->first; } /// @brief 最小値を返し、削除する T pop_min() { if(this->empty())return not_found; auto mn=*this->begin(); T ret=mn.first; this->erase(mn); return ret; } /// @brief 最大値を返し、削除する T pop_max() { if(this->empty())return not_found; auto mx=*this->rbegin(); T ret=mx.first; this->erase(mx); return ret; } /// @brief x が含まれているか否かを返す bool contains(T x) { auto itr=this->lower_bound({x,0}); if(itr==this->end())return false; return itr->first==x; } /// @brief x の個数を返す int count(T x) { if(!contains(x))return 0; auto itr=this->lower_bound({x+1,0}); itr--; return itr->second+1; } /// @brief x を削除する /// @brief x が含まれていたか否かを返す bool discard(T x) { if(!contains(x))return false; auto itr=prev(this->lower_bound({x+1,0})); if(itr==this->end())return false; this->erase(itr); return true; } /// @brief x より大きい最小の値を返す T gt(T x) { auto itr=this->lower_bound({x+1,0}); if(itr==this->end())return not_found; return itr->first; } /// @brief x 以上最小の値を返す T ge(T x) { auto itr=this->lower_bound({x,0}); if(itr==this->end())return not_found; return itr->first; } /// @brief x 未満最大の値を返す T lt(T x) { auto itr=this->lower_bound({x,0}); if(itr==this->begin())return not_found; return(--itr)->first; } /// @brief x 以下最大の値を返す T le(T x) { auto itr=this->lower_bound({x+1,0}); if(itr==this->begin())return not_found; return(--itr)->first; } /// @brief x 未満の値の個数を返す int count_lt(T x) { return this->order_of_key({x,0}); } /// @brief x 以下の値の個数を返す int count_le(T x) { return this->order_of_key({x+1,0}); } /// @brief x より大きい値の個数を返す int count_gt(T x) { return this->size()-this->order_of_key({x+1,0}); } /// @brief x 以上の値の個数を返す int count_ge(T x) { return this->size()-this->order_of_key({x,0}); } /// @brief k(0-indexed) 番目に小さい値の個数を返す T kth_min(int k) { return this->find_by_order(k)->first; } /// @brief k(0-indexed) 番目に大きい値の個数を返す T kth_max(int k) { return this->find_by_order(this->size()-k-1)->first; } }; //---------------------------------------------------------- void solve() { int N,K,Q; cin>>N>>K>>Q; vector A(N); REP(i,N) cin>>A[i]; SortedMultiTree st(-1); REP(i,N) st.add(A[i]); while(Q--) { int t; cin>>t; if(t==1) { ll x; cin>>x; st.add(x); } else if(t==2) { ll y; cin>>y; ll x=st.kth_min(K-1); st.discard(x); st.add(x+y); } else { ll x=st.kth_min(K-1); cout<>T; while(T--) solve(); }