/*
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#include<bits/stdc++.h>
using namespace std;
const int N=30005;
int inline read()
{
	int num=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
	return num*f;
}
int n,m,tot,mod,siz,bel[N],a[N],c[N];
int L=1,R,cnt[N],ans[N];
struct data{int l,r,id;}d[N];
bool operator <(data A,data B){return bel[A.l]==bel[B.l]?(bel[A.l]&1?A.r<B.r:A.r>B.r):A.l<B.l;}
int inc(int x,int y){return x+y>=mod?x+y-mod:x+y;}
struct Matrix
{
	int M[4];
	Matrix(){memset(M,0,sizeof(M));}
	void reset(){M[0]=1;M[1]=0;M[2]=0;M[3]=1;}
	int &operator [](const int x){return M[x];}
	Matrix friend operator +(Matrix A,Matrix B)
	{
		Matrix res;
		res[0]=inc(A[0],B[0]);
		res[1]=inc(A[1],B[1]);
		res[2]=inc(A[2],B[2]);
		res[3]=inc(A[3],B[3]);
		return res;
	}
	Matrix friend operator *(Matrix A,Matrix B)
	{
		Matrix res;
		res[0]=(1ll*A[0]*B[0]+1ll*A[1]*B[2])%mod;
		res[1]=(1ll*A[0]*B[1]+1ll*A[1]*B[3])%mod;
		res[2]=(1ll*A[2]*B[0]+1ll*A[3]*B[2])%mod;
		res[3]=(1ll*A[2]*B[1]+1ll*A[3]*B[3])%mod;
		return res;
	}
	Matrix friend operator *(Matrix a,int x)
	{
		if(x==1)return a;
		a[0]=(1ll*a[0]*x)%mod;
		a[1]=(1ll*a[1]*x)%mod;
		a[2]=(1ll*a[2]*x)%mod;
		a[3]=(1ll*a[3]*x)%mod;
		return a;
	}
}fib[N],inv[N];
int w[N<<2],tag[N<<2];Matrix t[N<<2];
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
void up(int k)
{
	Matrix A=t[ls],B=t[rs];
	if(w[ls]!=1)A=A*w[ls];
	if(w[rs]!=1)B=B*w[rs];
	t[k]=A+B;
}
void up(int k){t[k]=(t[ls]*w[ls])+(t[rs]*w[rs]);}
void LT(int k,int v){if(v>0)t[k]=t[k]*fib[v];else t[k]=t[k]*inv[-v];tag[k]+=v;}
void down(int k){if(tag[k])LT(ls,tag[k]),LT(rs,tag[k]),tag[k]=0;}
void insert(int k,int l,int r,int q)
{
	if(l==r)return w[k]=c[q],void();
	down(k);
	if(q<=mid)insert(ls,l,mid,q),LT(rs,1);
	else insert(rs,mid+1,r,q);
	up(k);
}
void erase(int k,int l,int r,int q)
{
	if(l==r)return w[k]=0,void();
	down(k);
	if(q<=mid)erase(ls,l,mid,q),LT(rs,-1);
	else erase(rs,mid+1,r,q);
	up(k);
}
void add(int x){if(!cnt[x])insert(1,1,tot,x);cnt[x]++;}
void del(int x){cnt[x]--;if(!cnt[x])erase(1,1,tot,x);}
int main(){
	n=read();mod=read();
	for(int i=1;i<=n;i++)c[i]=a[i]=read();
	sort(c+1,c+1+n);tot=unique(c+1,c+1+n)-c-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(c+1,c+1+tot,a[i])-c;
	fib[1][0]=1;fib[1][1]=1;fib[1][2]=1;fib[1][3]=0;
	inv[1][0]=0;inv[1][1]=1;inv[1][2]=1;inv[1][3]=mod-1;
	for(int i=2;i<=tot;i++)
	{
		fib[i]=fib[1]*fib[i-1];
		inv[i]=inv[1]*inv[i-1];
	}
	m=read();siz=ceil(n/sqrt(m));
	for(int i=1;i<=m;i++)d[i]=(data){read(),read(),i};
	for(int i=1;i<=n;i++)bel[i]=(i-1)/siz+1;
	sort(d+1,d+1+m);
	build(1,1,tot);
	for(int i=1;i<=m;i++)
	{
		while(L>d[i].l)add(a[--L]);
		while(R<d[i].r)add(a[++R]);
		while(L<d[i].l)del(a[L++]);
		while(R>d[i].r)del(a[R--]);
		ans[d[i].id]=t[1][2];
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}