CODE:

#include 

long long getno(int i,int j) {
	long long sum=i+j-2;
	long long start=sum*(sum+1)/2;
	return start+j;
};

void getints(int* a,int* b,int i) {
	int pos=1,now=1;
	while(pos
#include 

typedef struct {
	long long p,q;
} pq_t;

int K,N;
pq_t pq[100000];
char invalidFlag[100000];

/* syo-zyun */
int qsort_comp(const void* x,const void* y) {
	const pq_t* a=(const pq_t*)x;
	const pq_t* b=(const pq_t*)y;
	if(a->p>b->p)return 1;
	if(a->pp)return -1;
	if(a->q>b->q)return 1;
	if(a->qq)return -1;
	return 0;
}

long long pos2num(int K,int p) {
	return (1LL=0;i--,now=(now+1)/2) {
		target.p=i;
		target.q=now;
		if(bsearch(&target,pq,N,sizeof(pq_t),qsort_comp))return 1;
	}
	return 0;
}

int main(void) {
	int i;
	long long count;
	scanf("%d%d",&K,&N);
	K++;
	for(i=0;i

long long mysqrt(long long n) {
	long long left,right;
	long long mid;
	if(n==0)return 0;
	if(n10000000ll)right=mid-1;/* avoid overflow */
		else {
			if(mid*mid==n)return mid;
			else if(mid*mid=2;i--) {
		sum+=i*i-now;
		sum++;
		now=i;
	}
	printf("%lld\n",sum);
	return 0;
}

CODE:

#include 
#include 

int K,R;
char omap[3000001];
char fmap[3000001];
int omemo[3000001];
int fmemo[3000001];
int pmemo[10)return fmemo[pos]-1;
	if(fmap[pos])return 0;
	if(pos==0) {
		int i;
		for(i=0;iK)return 0;
	/*if(omemo[pos]>0)return omemo[pos]-1;*/
	if(omap[pos])return 0;
	if(pos==K) {
		memset(fmemo,0,sizeof(fmemo));
		if(pmemo[puttern]>0)return pmemo[puttern]-1;
		pmemo[puttern]=(result=ftansaku(K))+1;
	} else {
		puttern|=1

int N,Q,P;
int suuretu[100001];

int nummap[1000001];
long long ruisekiwa[100001];

int getone(int x,int c) {
	long long buffer=x;
	long long result=1;
	while(c>0) {
		if(c&1) {
			result=(result*buffer)%P;
		}
		buffer=(buffer*buffer)%P;
		c>>=1;
	}
	return (int)result;
}

int main(void) {
	int i;
	scanf("%d%d%d",&N,&Q,&P);
	for(i=1;i<=N;i++)scanf("%d",&suuretu[i]);
	for(i=1;i<=N;i++) {
		nummap[suuretu[i]]++;
		ruisekiwa[i]=getone(suuretu[i],nummap[suuretu[i]]);
	}
	for(i=1;i<=N;i++) {
		ruisekiwa[i]+=ruisekiwa[i-1];
	}
	for(i=0;i<Q;i++) {
		int s,t;
		scanf("%d%d",&s,&t);
		printf("%lld\n",(ruisekiwa[t]-ruisekiwa[s-1])%P);
	}
	return 0;
}