线段树二：

#include<bits/stdc++.h>
#define ll long long
#define int long long
const int MAX=1e5+10;
const int MOD=571373;
using namespace std;
inline int read() {
  int fh = 1, res = 0; char ch = getchar();
  for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
  for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
  res = res * fh;
  return res;
}
inline void write(ll x) {
	if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct tree{int l,r,w,f1,f2;}a[MAX<<2];
int ans;
inline int lc(int k){return k<<1;}
inline int rc(int k){return k<<1|1;}
inline void build(int k,int l,int r)
{
	a[k].l=l;a[k].r=r;
	a[k].f1=1; 
	if(l==r)
	{
		a[k].w=read();
		return ;
	}
	int mid=(l+r)>>1;
	build(lc(k),l,mid);
	build(rc(k),mid+1,r);
	a[k].w=a[lc(k)].w+a[rc(k)].w;
}	
inline void down(int k)
{
	a[lc(k)].f1=(a[lc(k)].f1*a[k].f1)%MOD;
	a[rc(k)].f1=(a[rc(k)].f1*a[k].f1)%MOD;
	a[lc(k)].f2=(a[lc(k)].f2*a[k].f1+a[k].f2)%MOD;
	a[rc(k)].f1=(a[rc(k)].f2*a[k].f1+a[k].f2)%MOD;
	a[lc(k)].w=(a[lc(k)].w*a[k].f1+a[k].f2*(a[lc(k)].r-a[lc(k)].l+1))%MOD;
	a[rc(k)].w=(a[rc(k)].w*a[k].f1+a[k].f2*(a[rc(k)].r-a[rc(k)].l+1))%MOD;
	a[k].f1=1;
	a[k].f2=0;
	return ;
}
inline void ask(int k,int x,int y)
{
	if(x<=a[k].l&&y>=a[k].r)
	{
		ans=(ans+a[k].w)%MOD;
		return ;
	}
	if(a[k].f1||a[k].f2) down(k);
	int m=(a[k].l+a[k].r)>>1;
	if(x<=m) ask(lc(k),x,y);
	if(y>=m+1) ask(rc(k),x,y);
}
inline void change1(int x,int y,int z,int k)
{
	if(x<=a[k].l&&y>=a[k].r)
	{
		a[k].w=(a[k].w+(a[k].r-a[k].l+1)*z)%MOD;
		a[k].f2=(a[k].f2+z)%MOD;
		return ;
	}
	if(a[k].f1||a[k].f2) down(k);
	int m=(a[k].l+a[k].r)>>1;
	if(x<=m) change1(x,y,z,lc(k));
	if(y>=m+1) change1(x,y,z,rc(k));
	a[k].w=a[lc(k)].w+a[rc(k)].w;
}
inline void change2(int x,int y,int z,int k)
{
	if(x<=a[k].l&&y>=a[k].r)
	{
		a[k].w=(a[k].w*z)%MOD;
		a[k].f1=(a[k].f1*z)%MOD;
		return ;
	}
	if(a[k].f1) down(k);
	int m=(a[k].l+a[k].r)>>1;
	if(x<=m) change2(x,y,z,lc(k));
	if(y>=m+1) change2(x,y,z,rc(k));
	a[k].w=a[lc(k)].w+a[rc(k)].w;
}
signed main()
{
	int n=read(),m=read();
	build(1,1,n);
	while(m--)
	{
		int op=read();
		if(op==1)
		{
			int x=read(),y=read(),k=read();
			change1(x,y,k,1);
		}
		if(op==2)
		{
			int x=read(),y=read(),k=read();
			change2(x,y,k,1);
		}
		if(op==3)
		{
			int x=read(),y=read();
			ans=0;
			ask(1,x,y);
			write(ans%MOD);
			putchar('\n');
		}
	} 
	return 0;
}