rt，难道是我复杂度假了？？？跟 $n^2$ 跑一个分

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
using namespace std;

#define lint long long

/***** Fast_IO *****/

using vii = std::vector<int> ;
using pii = std::pair<int,int> ;

namespace IO{
	char buf[(1<<21)],*p1=buf,*p2=buf,buf1[(1<<21)]; int _=0;

	#define gc getchar
	#define pc putchar

	template<class I>
	inline I read(I &x){
		x=0; I f=1; char c=gc(); if(c==EOF){ return -1; }
		while(c<'0'||c>'9'){ if(c=='-'){ f=f*(-1); } c=gc(); }
		while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
		return x=x*f;
	}

	template<typename I,typename ...Args>
	inline void read(I &a, Args &...args){
		read(a),read(args...);
	}

	template<class I>
	inline void write(I x){
		if(x==0){ pc('0'); return; }
		I tmp=x>0?x:(-x),cnt=0;
		if(x<0){ pc('-'); }
		while(tmp){ buf[cnt++]=(tmp%10)+'0'; tmp/=10; }
		while(cnt){ pc(buf[--cnt]); }
		return;
	}

	template<class I>
	inline void chmax(I &x,I y){ return x=max(x,y),void(); }

	template<class I>
	inline void chmin(I &x,I y){ return x=min(x,y),void(); }
	
	template<int a,class I>
	inline int in(I x,I y){ return a>x&&a<y; }

	#define out(x) write(x),pc(' ')
	#define outn(x) write(x),pc('\n')
	#define assi() pc('\t')
	#define FOR(i,a,b) for(int i(a);i<=(b);++i)
	#define ROF(i,a,b) for(int i(a);i>=(b);--i)
	#define FORs(i,a,b,s) for(int i(a);i<=(b);i+=(s))
	#define ROFs(i,a,b,s) for(int i(a);i>=(b);i-=(s))
	#define next(i,now) for(int i(link[now]);i;i=edge[i].nexty)
	#define umap unordered_map 
	#define each(i,v) for(auto &i:v)
	#define all(v) v.begin(),v.end()
	#define sqr(k) ((k)*(k))
	#define inf 0x3f3f3f3f3f3f
	#define pb push_back
	#define mp make_pair
	#define DB double
	#define fir first
	#define sec second
}using namespace IO;

/***** Fast_IO *****/

#define maxn 1000010
#define SIZE 5010

int mod;
int n,m,a[maxn];

namespace BLOCK{
	int siz,Cnt;
	int L[maxn];
	int R[maxn];
	int bel[maxn];
	int add[maxn];
	int pro[maxn];
	int sum[maxn];

	void init(){
		siz=(int)sqrt(n);
		FOR(i,1,n){ bel[i]=(i-1)/siz+1; (sum[bel[i]]+=a[i])%=mod; } Cnt=bel[n];
		FOR(i,1,Cnt){ L[i]=(i-1)*siz+1; R[i]=min(n,i*siz); pro[i]=1; }
		return;
	}

	void reset(int x){
		sum[x]=0;
		FOR(i,L[x],R[x]){ a[i]=1ll*a[i]*pro[x]%mod; a[i]=(a[i]+add[x])%mod; (sum[x]+=a[i])%=mod; }
		pro[x]=1,add[x]=0; return;
	}

	void Add(int l,int r,int c){
		if(bel[l]==bel[r]){ reset(bel[l]); FOR(i,l,r){ a[i]=(a[i]+c)%mod; (sum[bel[i]]+=c)%=mod; } return; }
		reset(bel[l]); FOR(i,l,R[bel[l]]){ a[i]=(a[i]+c)%mod; (sum[bel[i]]+=c)%=mod; }
		reset(bel[r]); FOR(i,L[bel[r]],r){ a[i]=(a[i]+c)%mod; (sum[bel[i]]+=c)%=mod; }
		FOR(i,bel[l]+1,bel[r]-1){ (add[i]+=c)%=mod; (sum[i]+=1ll*(R[i]-L[i]+1)*c%mod)%=mod; }
		return;
	}

	void Mul(int l,int r,int c){
		if(bel[l]==bel[r]){ reset(bel[l]); FOR(i,l,r){ ((sum[bel[i]]-=a[i])+=mod)%=mod; a[i]=1ll*a[i]*c%mod; (sum[bel[i]]+=a[i])%=mod; } return; }
		reset(bel[l]); FOR(i,l,R[bel[l]]){ ((sum[bel[i]]-=a[i])+=mod)%=mod; a[i]=1ll*a[i]*c%mod; (sum[bel[i]]+=a[i])%=mod; }
		reset(bel[r]); FOR(i,L[bel[r]],r){ ((sum[bel[i]]-=a[i])+=mod)%=mod; a[i]=1ll*a[i]*c%mod; (sum[bel[i]]+=a[i])%=mod; }
		FOR(i,bel[l]+1,bel[r]-1){ add[i]=1ll*add[i]*c%mod; pro[i]=1ll*pro[i]*c%mod; sum[i]=1ll*sum[i]*c%mod; }
		return;
	}

	int Que(int l,int r){
		int res=0;
		if(bel[l]==bel[r]){ reset(bel[l]); FOR(i,l,r){ (res+=a[i])%=mod; } return res; }
		reset(bel[l]); FOR(i,l,R[bel[l]]){ (res+=a[i])%=mod; }
		reset(bel[r]); FOR(i,L[bel[r]],r){ (res+=a[i])%=mod; }
		FOR(i,bel[l]+1,bel[r]-1){ (res+=sum[i])%=mod; } return res;
	}
};

int main(){
	read(n,m,mod);
	FOR(i,1,n){ read(a[i]); a[i]%=mod; }
	BLOCK::init();
	while(m--){
		int opt,l,r,c;
		read(opt,l,r);
		switch(opt){
			case 1:{
				read(c);
				BLOCK::Mul(l,r,c);
				break;
			} case 2:{
				read(c);
				BLOCK::Add(l,r,c);
				break;
			} case 3:{
				outn( BLOCK::Que(l,r) );
				break;
			}
		}
	}
	return 0;
}

/*
8 10 571373
5929 7152 8443 6028 8580 5449 8473 4237 
2 4 8 4376
1 2 8 9637
2 2 6 7918
2 5 8 5681
3 2 8
1 1 5 6482
3 1 5
1 5 8 8701
2 5 8 7992
2 5 8 7806
*/

/*
478836
562114
*/