本题需要使用扩展欧拉定理。

注意到经过$2log(m)$次\phi的复合后函数值减少为$1$。

当$n$为偶数时，一定有$n/2$个数与n有共同因子$2$，$\phi(n)<=n/2$。

当$n$为奇数时，一定有$n-i!=i$，考虑更相减法，$gcd(n,i)=gcd(n,n-i)$，与$n$互质的数一定成对出现，$\phi(n)$为偶数。

所以至多两次操作后$m$会减少一半。

对于每次询问，暴力计算即可。复杂度$O(qlog(m))$

std::vector<int> phi;
int euler(int n){
	int ans=n;
	for(int i=2;i<=n/i;i++){
		if(n%i!=0)continue;
		ans=ans/i*(i-1);
		while(n%i==0)n/=i;
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}
void init(int m){
	phi.push_back(m);
	while(m!=1){
		m=euler(m);
		phi.push_back(m);
	}
}
void solve(){
	int n,m,q;std::cin>>n>>m>>q;
	init(m);
	std::vector<int> w(n+1);
	for(int i=1;i<=n;i++)std::cin>>w[i];
	auto cal=[&](int l,int r){
		r=std::min(r,l-1+(int)phi.size());
		int res=1;
		for(int i=r;i>=l;i--){
			bool ok=false;
			auto power=[&](int a,int b,int mod){
				int ans=1%mod;
				while(b){
					if(b&1){
						ans=ans*a;
						if(ans>=mod){
							ans%=mod;
							ok=true;
						}
					}
					a=a*a;
					if(a>=mod){
						ok=true;
						a%=mod;
					}
					b>>=1;
				}
				return ans;
			};
			res=power(w[i],res,phi[i-l]);
			if(ok)res+=phi[i-l];
		}
		std::cout<<res%phi[0]<<'\n';
	};
	while(q--){
		int l,r;std::cin>>l>>r;
		cal(l,r);
	}
}