rt，全RE。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100005
int n,m,op,p;
int a[maxn];
struct node{
	int l,r,sum,mul,lazysum,lazymul;
}t[maxn << 2];
void update(int id){
	t[id].sum=t[id<<1].sum*t[id<<1].sum+(t[id<<1].r-t[id<<1].l+1)*t[id<<1].lazysum+t[id<<1|1].sum*t[id<<1].lazymul+(t[id<<1|1].r-t[id<<1|1].l+1)*t[id<<1|1].lazysum;
	t[id].sum%=p;
	return;
}
void buildtree(int id,int l,int r){
	t[id].l=l;
	t[id].r=r;
	if(l==r){
		t[id].sum=a[l]%p;
		return; 
	}
	int mid=(l+r)>>1;
	buildtree(id<<1,l,mid);
	buildtree(id<<1|1,mid+1,r);
	update(id);
	return;
}
void pushdown(int id){
	t[id<<1].lazysum*=t[id<<1].lazymul;
	t[id<<1].lazymul*=t[id<<1].lazymul;
	t[id<<1].lazysum+=t[id<<1].lazysum;
	t[id<<1].lazysum%=p;
	t[id<<1].lazymul%=p;
	t[id<<1|1].lazysum*=t[id<<1].lazymul;
	t[id<<1|1].lazymul*=t[id<<1].lazymul;
	t[id<<1|1].lazysum+=t[id<<1].lazysum;
	t[id<<1|1].lazysum%=p;
	t[id<<1|1].lazymul%=p;
	t[id].sum*=t[id].lazymul;
	t[id].l+=t[id].lazysum*(t[id].r-t[id].l+1);
	t[id].sum%=p;
	t[id].lazysum=0;
	t[id].lazymul=1;
	return;
}
void add(int id,int l,int r,int val){
	if(l<=t[id].l && t[id].r<=r){
		t[id].lazysum+=val;
		t[id].sum+=(t[id].r-t[id].l+1)*val;
		return;
	}
	pushdown(id);
	int mid=(t[id].l+t[id].r)>>1;
	if(l<=mid) add(id<<1,l,r,val);
	if(r>mid) add(id<<1|1,l,r,val);
	update(id);
	return;
}
void mul(int id,int l,int r,int val){
	if(l<=t[id].l && t[id].r<=r){
		t[id].lazymul*=val;
		t[id].lazymul%=p;
		t[id].lazysum*=val;
		t[id].lazysum%=p; 
		return;
	}
	pushdown(id);
	int mid=(t[id].l+t[id].r)>>1;
	if(l<=mid) add(id<<1,l,r,val);
	if(r>mid) add(id<<1|1,l,r,val);
	update(id);
	return;
}
int query(int id,int l,int r){
	if(l<=t[id].l && r>=t[id].r){
		return t[id].sum;
	}
	pushdown(id);
	int mid=(t[id].l+t[id].r)>>1,ans=0;
	if(l<=mid) ans+=query(id<<1,l,r);
	if(r>mid) ans+=query(id<<1|1,l,r);
	return ans;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	buildtree(1,1,n);
	while(m--){
		cin >> op;
		if(op==1){
			int x,y,k;
			cin >> x >> y >> k;
			mul(1,x,y,k);
		}
		else if (op==2){
			int x,y,k;
			cin >> x >> y >> k;
			add(1,x,y,k);
		}
		else{
			int x,y;
			cin >> x >> y;
			cout << query(1,x,y) << '\n';
		}
	}
	return 0;
}