• 题目中的过程等价于：重复 $mk$ 次，每次选择最大的还未被选择 $m$ 次的数，将其减少 1。
• 最后的数列一定形如：最小的一些数不变，之后一段 $t - 1$ 和一段 $t$，最大的若干个数减少 $m$，且减少后 $\geq t$。
• 二分 $t$ 的值，用树状数组求出能减少的次数。然后求出上述的段，就能回答所有询问。
• 时间复杂度 $O((n + q) \log^2 n)$。

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
const int N=4e5+10;
struct BIT{
	int tr[N];
	inline void add(int x,int y){for(;x<N;x+=x&-x)tr[x]+=y;}
	inline int get(int x){int sum=0;for(;x;x-=x&-x)sum+=tr[x];return sum;}
	inline int query(int l,int r){l=max(l,1ll);if(l>r)return 0;return get(r)-get(l-1);}
}cnt,val;
int n,a[N],q,op[N],m[N],k[N],l[N],r[N],to[N],cn;
inline int chk(int t,int m){
	int u=upper_bound(to+1,to+1+cn,t+m)-to,v=lower_bound(to+1,to+1+cn,t)-to;
	return m*cnt.query(u,cn)+val.query(v,u-1)-t*cnt.query(v,u-1);
}
inline int query(int l,int r,int d){
	if(l>r)return 0;
	int L=l,R=r+1;
	while(L<R){
		int mid=(L+R+1)>>1;
		if(cnt.query(mid,r)<d)R=mid-1;
		else L=mid;
	}
	return val.query(L,r)+to[L]*(d-cnt.query(L,r));
}
inline int solve(int t,int m,int mlen,int q){
	if(!q)return 0;
	int ans=0,u=upper_bound(to+1,to+1+cn,t+m)-to;
	int x=cnt.query(u,cn);
	if(x<q)ans+=val.query(u,cn)-m*cnt.query(u,cn),q-=x;
	else{
		ans+=query(u,cn,q)-m*q;
		return ans;
	}u--;
	int v=lower_bound(to+1,to+1+cn,t-1)-to;
	x=cnt.query(v,u);
	if(x<q)ans+=(t-1)*(x-mlen)+t*mlen,q-=x;
	else{
		if(q<=mlen)ans+=t*q;
		else ans+=(t-1)*(q-mlen)+t*mlen;
		return ans;
	}
	return ans+query(1,v-1,q);
}
inline int work(int m,int k,int ql,int qr){
	int l=-2e9,r=to[cn];
	while(l<r){
		int t=(l+r)>>1;
		if(chk(t,m)>m*k)l=t+1;
		else r=t;
	}
	int t=l,mlen=chk(t-1,m+1)-m*k-chk(t+m,1);
	return solve(t,m,mlen,n-ql+1)-solve(t,m,mlen,n-qr);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m[0]>>k[0]>>q;
	for(int i=1;i<=n;i++)cin>>a[i],to[++cn]=a[i];
	for(int i=1;i<=q;i++){
		cin>>op[i];
		if(op[i]==1)cin>>m[i]>>k[i]>>l[i],r[i]=l[i];
		if(op[i]==2)cin>>m[i]>>k[i],to[++cn]=k[i];
		if(op[i]==3)cin>>m[i]>>k[i]>>l[i]>>r[i];
	}
	sort(to+1,to+1+cn),cn=unique(to+1,to+1+cn)-to-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(to+1,to+1+cn,a[i])-to;
	for(int i=1;i<=q;i++)if(op[i]==2)k[i]=lower_bound(to+1,to+1+cn,k[i])-to;
	for(int i=1;i<=n;i++)cnt.add(a[i],1),val.add(a[i],to[a[i]]);
	for(int i=1;i<=n;i++)cout<<work(m[0],k[0],i,i)<<" ";cout<<"\n";
	for(int i=1;i<=q;i++){
		if(op[i]==2)cnt.add(a[m[i]],-1),val.add(a[m[i]],-to[a[m[i]]]),a[m[i]]=k[i],cnt.add(a[m[i]],1),val.add(a[m[i]],to[a[m[i]]]);
		else cout<<work(m[i],k[i],l[i],r[i])<<"\n";
	}
	return 0;
}