主要是操作三，怎么计算
那么只需要维护区间和和区间平方和即可，1/2用逆元
多个标记注意标记之间有没有影响，mod其实很简单的，但是我标记没处理好一直wa,mod乱搞一下，我mod很丑
#include<iostream>
#include<algorithm>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=1e5+9;
ll a[N];
ll n,m,mod;
struct node{ll val,pfval,mul,add;
}seg[N<<2];
ll tl(ll x){return x<<1;
}
ll tr(ll x){return x<<1|1;
}
ll qmi(ll a,ll b){ll res=1;while(b){if(b&1){res=res*a%mod;}b>>=1;a=a*a%mod;}return res%mod;
}
ll inv(ll x){return qmi(x,mod-2)%mod;
}
void pushup(int id){seg[id].val=(seg[tl(id)].val%mod)+(seg[tr(id)].val%mod);seg[id].pfval=(seg[tl(id)].pfval%mod)+(seg[tr(id)].pfval%mod);
}
void build(int id,int l,int r){seg[id].mul=1;seg[id].add=0;if(l==r){seg[id].val=a[l]%mod;seg[id].pfval=a[l]*a[l]%mod;}else{int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}
}
bool inrange(int L,int R,int l,int r){return L>=l && R<=r;
}
bool outofrange(int L,int R,int l,int r){return L>r || l>R;
}
void maketag(int id,int l,int r,ll v,int opt){if(opt==1){v%=mod;seg[id].val*=v;seg[id].val%=mod;seg[id].mul*=v;seg[id].mul%=mod;v=(v%mod)*v%mod;seg[id].pfval*=v;(seg[id].add*=v)%=mod;seg[id].pfval%=mod;}else{v%=mod;seg[id].pfval+=((v%mod)*v%mod)*(r-l+1)%mod+2*(v%mod)*(seg[id].val%mod);seg[id].pfval%=mod;seg[id].val+=(r-l+1)*(v%mod); seg[id].val%=mod;seg[id].add+=v;seg[id].add%=mod;}
}
void pushdown(int id,int l,int r){int mid=(l+r)>>1;if(seg[id].mul!=1){maketag(tl(id),l,mid,seg[id].mul,1);maketag(tr(id),mid+1,r,seg[id].mul,1);}if(seg[id].add){maketag(tl(id),l,mid,seg[id].add,2);maketag(tr(id),mid+1,r,seg[id].add,2);}seg[id].mul=1;seg[id].add=0;
}
ll querysum(int id,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[id].val%mod;}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);return querysum(tl(id),L,mid,l,r)%mod+querysum(tr(id),mid+1,R,l,r)%mod;}else{return 0;}
}
ll querypfsum(int id,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[id].pfval%mod;}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);return querypfsum(tl(id),L,mid,l,r)%mod+querypfsum(tr(id),mid+1,R,l,r)%mod;}else{return 0;}
}
void modifymul(int id,int L,int R,int l,int r,ll v){if(inrange(L,R,l,r)){maketag(id,L,R,v,1);}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);modifymul(tl(id),L,mid,l,r,v);modifymul(tr(id),mid+1,R,l,r,v);pushup(id);}
}
void modifyadd(int id,int L,int R,int l,int r,ll v){if(inrange(L,R,l,r)){maketag(id,L,R,v,2);}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);modifyadd(tl(id),L,mid,l,r,v);modifyadd(tr(id),mid+1,R,l,r,v);pushup(id);}
}
void solve(){cin>>n>>m>>mod;for(int i=1;i<=n;i++){cin>>a[i];a[i]%=mod;}build(1,1,n);for(int i=1;i<=m;i++){int opt;cin>>opt;if(opt==1){int l,r,v;cin>>l>>r>>v;modifyadd(1,1,n,l,r,v);}else if(opt==2){int l,r,v;cin>>l>>r>>v;modifymul(1,1,n,l,r,v);}else{int l,r;cin>>l>>r;ll res1=querysum(1,1,n,l,r)%mod;res1=res1*res1%mod;ll res2=querypfsum(1,1,n,l,r)%mod;res2%=mod;ll ans=(((res1-res2)%mod+mod)%mod)*inv(2)%mod;cout<<ans%mod<<'\n';}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}
)
)
