AC on #1 #3 #4

#include<bits/stdc++.h>
#define mod 571373
using namespace std;
int n,q,m;
long long a[100005];
struct node{
	long long v,lzy1,lzy2;
//	lzy1乘法，lzy2加法 
}tr[400005];
void build(int p,int l,int r){
	if(l==r){
		tr[p].v=a[l];
	}
	else{
		tr[p].lzy1=1;
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		tr[p].v=tr[p<<1].v+tr[p<<1|1].v;
	}
	tr[p].v%=mod;
}
void pushdown(int p,int len){
	tr[p<<1].v=(tr[p<<1].v*tr[p].lzy1+tr[p].lzy2*(len-len/2))%mod;
	tr[p<<1|1].v=(tr[p<<1|1].v*tr[p].lzy1+tr[p].lzy2*(len/2))%mod;
	(tr[p<<1].lzy1*=tr[p].lzy1)%=mod;
	(tr[p<<1|1].lzy1*=tr[p].lzy1)%=mod;
	(tr[p<<1].lzy2+=tr[p].lzy2)%=mod;
	(tr[p<<1|1].lzy2+=tr[p].lzy2)%=mod;
	tr[p].lzy1=1;
	tr[p].lzy2=0;
}
void mult(int l,int r,long long k,int p,int cl,int cr){
	if(l>cr||cl>r)return;
	if(l<=cl&&cr<=r){
		(tr[p].v*=k)%=mod;
		if(cr>cl){
			(tr[p].lzy1*=k)%=mod;
			(tr[p].lzy2*=k)%=mod;
		}
		return;
	}
	pushdown(p,cr-cl+1);
	int mid=cl+cr>>1;
	mult(l,r,k,p<<1,cl,mid);
	mult(l,r,k,p<<1|1,mid+1,cr);
	tr[p].v=tr[p<<1].v+tr[p<<1|1].v;
	tr[p].v%=mod;
}
void update(int l,int r,long long k,int p,int cl,int cr){
	if(l>cr||cl>r)return;
	if(l<=cl&&cr<=r){
		(tr[p].v+=(cr-cl+1)*k%mod)%=mod;
		if(cr>cl)(tr[p].lzy2+=k)%=mod;
		return;
	}
	pushdown(p,cr-cl+1);
	int mid=cl+cr>>1;
	update(l,r,k,p<<1,cl,mid);
	update(l,r,k,p<<1|1,mid+1,cr);
	tr[p].v=tr[p<<1].v+tr[p<<1|1].v;
	tr[p].v%=mod;
}
long long query(int l,int r,int p,int cl,int cr){
	if(l>cr||cl>r)return 0;
	if(l<=cl&&cr<=r){
		return tr[p].v%mod;
	}
	pushdown(p,cr-cl+1);
	int mid=cl+cr>>1;
	return (query(l,r,p<<1,cl,mid)+query(l,r,p<<1|1,mid+1,cr))%mod;
}
int main(){
	scanf("%d%d%d",&n,&q,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	while(q--){
		int opt,x,y;
		long long k;
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1){
			scanf("%lld",&k);
			mult(x,y,k,1,1,n);
		}
		else if(opt==2){
			scanf("%lld",&k);
			update(x,y,k,1,1,n);
		}
		else{
			printf("%lld\n",query(x,y,1,1,n));
		}
	}
	return 0;
}