RT。本地的随机数据均表现在0.8s以内，但莫名其妙就TLE了。

以下是源代码：

#include<bits/stdc++.h>
#define N 105050
using namespace std;
struct node{
	int s[61],w,now,f,lz,l,r,len;
}t[N<<2];
int p;
int vis[N],len[N],a[N],b[N],n,m,gcd[65][65];
#define lc x<<1
#define rc x<<1|1
void pushup(int x){
	t[x].f=t[lc].f&t[rc].f;
	if(t[x].f){ 
		t[x].now=0;t[x].len=t[lc].len*t[rc].len/gcd[t[lc].len][t[rc].len];
//		assert(t[x].len<=60);
		for(int i=0;i<t[x].len;i++){
			t[x].s[i]=t[lc].s[(t[lc].now+i)%t[lc].len]+t[rc].s[(t[rc].now+i)%t[rc].len];
//			assert(t[x].s[i]<p*(t[x].r-t[x].l+1));
		}
	}
	else {
		t[x].w=0;
		if(t[lc].f)t[x].w+=t[lc].s[t[lc].now%t[lc].len];
		else t[x].w+=t[lc].w;
		if(t[rc].f)t[x].w+=t[rc].s[t[rc].now%t[rc].len];
		else t[x].w+=t[rc].w;
	}
}
void pushdown(int x){
	t[lc].now+=t[x].lz,t[rc].now+=t[x].lz;
	t[lc].lz+=t[x].lz,t[rc].lz+=t[x].lz;
	t[x].lz=0;
}
void pushdown_for(int x){//Forever changed 
	if(t[x].f){
		t[x].now++;t[x].lz++;
		return ;
	}
	if(t[x].l==t[x].r){
		t[x].w=t[x].w*t[x].w%p;
		if(vis[t[x].w]){
			t[x].f=1;t[x].len=len[t[x].w];int y=t[x].w;
			for(int i=0;i<t[x].len;i++){
				t[x].s[i]=y;y=y*y%p;
			}
			t[x].now=0;
		}
	}
	else {
		pushdown_for(lc);pushdown_for(rc);
		pushup(x);
	}
} 
void build(int x,int l,int r){
	t[x].l=l,t[x].r=r;
	if(l==r){
		t[x].w=a[l];t[x].f=0;
		if(vis[t[x].w]){
			t[x].f=1;t[x].len=len[t[x].w];int y=t[x].w;
			for(int i=0;i<t[x].len;i++){
				t[x].s[i]=y;y=y*y%p;
			}
			t[x].now=0;
		}
		return ;
	}int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(x);
}
void change(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		pushdown_for(x);return ;
	}
	int mid=l+r>>1;if(t[x].f)pushdown(x);
	if(L<=mid)change(lc,l,mid,L,R);
	if(mid<R)change(rc,mid+1,r,L,R);
	pushup(x);
}
int find(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		if(t[x].f)return t[x].s[t[x].now%t[x].len];
		return t[x].w;
	}
	int mid=l+r>>1,res=0;if(t[x].f)pushdown(x);
	if(L<=mid)res+=find(lc,l,mid,L,R);
	if(mid<R)res+=find(rc,mid+1,r,L,R);
	return res;
}
void init(){
	for(int i=0;i<=60;i++)gcd[i][0]=gcd[0][i]=i;
	for(int i=1;i<=60;i++)for(int j=1;j<=60;j++){
		gcd[i][j]=__gcd(i,j);
	}
	for(int i=1;i<p;i++){
		if(vis[i])continue;
		int res=1,t=i;vector<int>now;
		while(!b[t]){
			now.push_back(t);
			b[t]=res;t=t*t%p;
			++res;
		}
		int le=res-b[t];res=0;
		for(auto x:now)b[x]=0;
		while(!b[t]){
			vis[t]=1;len[t]=le;b[t]=1;t=t*t%p;
		}
		for(auto x:now)b[x]=0;
		now.clear();now.shrink_to_fit(); 
	}
}
int read(){
	int x=0;char ch=getchar();while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
void write(int x){
	if(x<10){
		putchar(x+'0');
	}
	else write(x/10),putchar((x%10)+'0');
}
signed main(){
	n=read(),m=read(),p=read();
	for(int i=1;i<=n;i++)a[i]=read();
	init();build(1,1,n);
	while(m--){
		int opt=read();if(opt==1){
			int l=read(),r=read();change(1,1,n,l,r);
		}
		else {
			int l=read(),r=read();write(find(1,1,n,l,r));putchar('\n');
		}
	}
}
/*		
3 3 11 
1 2 3
2 1 3
1 1 3
2 1 3
*/