记录编号	164875	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[thusc2015]平方运算	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	7.539 s
提交时间	2015-06-07 10:15:57	内存使用	115.60 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100005;

inline int gcd(int a, int b){return (!a) ? b : gcd(b % a, a);}
inline int lcm(int a, int b){return a / gcd(a, b) * b;}

struct Data{
	Data *nxt;
	int Sum;
}DT[maxn << 7], *DTiter = DT;
inline void *operator new(size_t) {return DTiter++;}
inline void sh(Data *&x){x = x->nxt;}//shift

int N, A[maxn], p;
bool Ring[maxn], vis[maxn], onp[maxn];

struct SegT{
	int L, R, mid, tag, len;
	Data *dt;
	SegT *ls, *rs;
	inline void push(){
		tag %= len;
		if(ls){
			ls->tag += tag, rs->tag += tag;
			while(tag)sh(ls->dt), sh(rs->dt), --tag;
		}
		else tag = 0;
	}
	inline void update(){
		Data *it = dt, *l = ls->dt, *r = rs->dt;
		if(!len){it->Sum = l->Sum + r->Sum;return;}
		for(int i = 1;i <= len;++i, sh(it), sh(l), sh(r))
			it->Sum = l->Sum + r->Sum;
	}
	inline void init_dt(){
		Data *it = dt;
		int t = dt->Sum, x = t * t % p;
		for(len = 1;x != t;x = x * x % p){
			it = (it->nxt = new Data);
			it->Sum = x;
			++len;
		}
		it->nxt = dt;
		return;
	}
	inline void merge_dt(){
		Data *it = dt;
		Data *l = ls->dt, *r = rs->dt;
		len = lcm(ls->len, rs->len);
		it->Sum = l->Sum + r->Sum;
		sh(l), sh(r);
		for(int i = 1;i < len;++i, sh(l), sh(r)){
			it = (it->nxt = new Data);
			it->Sum = l->Sum + r->Sum;
		}
		it->nxt = dt;
	}
	inline void Modify(int l, int r){ 
		if(L == l && R == r){
			if(!len){
				if(L == mid){
					dt->Sum = dt->Sum * dt->Sum % p;
					if(Ring[dt->Sum])init_dt();
					return;
				}
				ls->Modify(l, mid), rs->Modify(mid, r);
				if(ls->len && rs->len)merge_dt();
				else dt->Sum = ls->dt->Sum + rs->dt->Sum;
				return;
			}
			sh(dt);
			++tag;
			return;
		}
		if(tag)push();
		if(r <= mid)ls->Modify(l, r);
		else if(l >= mid)rs->Modify(l, r);
		else ls->Modify(l, mid), rs->Modify(mid, r);
		update();
	}
	inline int Query(int l, int r){
		if(L == l && R == r)return dt->Sum;
		if(tag)push();
		if(r <= mid)return ls->Query(l, r);
		if(l >= mid)return rs->Query(l, r);
		return ls->Query(l, mid) + rs->Query(mid, r);
	}
	inline void init(int, int);
}seg, Pool[maxn << 2], *iter = Pool;

inline void SegT::init(int l, int r){
	L = l, R = r, mid = (l + r) >> 1;
	tag = 0;
	dt = new Data;
	if(L == mid){
		len = 0;
		dt->Sum = A[L];
		if(Ring[A[L]])init_dt();
		return;
	}
	ls = iter++, rs = iter++;
	ls->init(l, mid), rs->init(mid, r);
	update();
}

inline void find(int x){
	onp[x] = vis[x] = true;
	int t = x * x % p;
	if(onp[t]){
		while(t != x)Ring[t] = true, t = t * t % p;
		Ring[x] = true;
		onp[x] = false;
		return;
	}
	if(!vis[t])find(t);
	onp[x] = false;
}

inline void work(){
	int M, opt, l, r;
	getd(N), getd(M), getd(p);
	for(int i = 1;i <= N;++i)getd(A[i]);
	for(int i = 1;i <= N;++i)if(!vis[A[i]])find(A[i]);
	seg.init(1, N+1);

	//for(int i = 0;i < p;++i)printf("%d ", Ring[i]);
	while(M--){
		getd(opt), getd(l), getd(r);
		if(opt)printf("%d\n", seg.Query(l, r+1));
		else seg.Modify(l, r+1);
	}
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(thusc2015_square);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif
	work();

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}