ll@n,@k--,@q,@a[n];
sortA(n,a);
priority_queue<ll>r,s;
rep(i,k){
	r.push(a[i]);
}
rep(i,k,n){
	s.push(-a[i]);
}
rep(q){
	ll@w;
	if(w==1){
		ll@x;
		r.push(x);
		x=r.top();
		r.pop();
		s.push(-x);
	}
	if(w==2){
		ll@y;
		ll x=s.top();
		s.pop();
		s.push(x-y);
	}
	if(w==3){
		ll x=s.top();
		wt(-x);
	}
}