#include using namespace std; int main(){ int n,k,q; cin>>n>>k>>q; int a[n]; for(int i=0;i>a[i]; priority_queue PQlow; priority_queue,greater> PQup; auto push=[&](long long x){ if(PQlow.top()<=x) PQup.push(x); else{ PQup.push(PQlow.top()); PQlow.pop(); PQlow.push(x); } }; auto popget=[&](){ long long ret=PQlow.top(); PQlow.pop(); PQlow.push(PQup.top()); PQup.pop(); return ret; }; sort(a,a+n); for(int i=0;i>op; if(op==1){ long long x; cin>>x; push(x); } if(op==2){ long long y; cin>>y; auto val=popget(); push(val+y); } if(op==3){ auto ans=popget(); cout<