#include<bits/stdc++.h>
#define rep(i,s,n) for(i=(s);i<(n);i++)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const int SZ = 3e4+8;
int M;
int fibs[SZ],vals[SZ],ar[SZ];
int st[4*SZ][2],lazy[4*SZ];
void preprocess()
{
	fibs[0] = 0;
	fibs[1] = 1;
	for(int i=2; i<SZ; i++)
		fibs[i] = (fibs[i-1] + fibs[i-2]) % M;
	for(int i=2; i<SZ; i+=2)
		fibs[i] = -fibs[i];
}
inline int modulo(int x,int m)
{
	x%=m;
	if(x<0)x+=m;
	return x;
}
// initially s = 0, e = N-1, x = position where added(overall), i=0,
// n = index of fibo to be added, toadd = true if element to be added, false to remove
// val is the array from which ai is taken
void update(int s,int e,int x,int i,int n,bool toadd)
{
	if(lazy[i]!=0)
	{
		int a,b,c,d;
		if(lazy[i]>0)
		{
			a = abs(fibs[lazy[i]+1]);
			b = c = abs(fibs[lazy[i]]);
			d = abs(fibs[lazy[i]-1]);
		}
		else if(lazy[i]<0)
		{
			a = fibs[-(lazy[i]+1)];
			b = c = fibs[-lazy[i]];
			d = fibs[-(lazy[i]-1)];
		}
		a = a*st[i][0];
		b = b*st[i][1];
		c = c*st[i][0];
		d = d*st[i][1];
		st[i][0] = modulo(a+b,M);
		st[i][1] = modulo(c+d,M);
		if(s!=e)
			lazy[2*i+1]+=lazy[i], lazy[2*i+2] += lazy[i];
		lazy[i] = 0;
	}
	if(x>e)
		return;
	if(x<s)
	{
		int a = st[i][0];
		int b = st[i][1];
		if(toadd)
		{
			st[i][0] = modulo(a+b,M);
			st[i][1] = a;
			if(s!=e)
				lazy[2*i+1]++,lazy[2*i+2]++;
		}
		else
		{
			st[i][0] = b;
			st[i][1] = modulo(a-b,M);
			if(s!=e)
				lazy[2*i+1]--,lazy[2*i+2]--;
		}
		return;
	}
	if(s==e)
	{
		if(toadd)
		{
			int xr = vals[s];
			st[i][0] = (xr*abs(fibs[n]))%M;
			st[i][1] = (xr*abs(fibs[n-1]))%M;
		}
		else
			st[i][0] = st[i][1] = 0;
		return;
	}
	int mid = (s+e)/2;
	update(s,mid,x,2*i+1,n,toadd);
	update(mid+1,e,x,2*i+2,n,toadd);
	int a = st[2*i+1][0],b = st[2*i+1][1];
	int c = st[2*i+2][0],d = st[2*i+2][1];
	st[i][0] = (a+c)%M;
	st[i][1] = (b+d)%M;
}
int sqn;
inline bool sub(pair<int,int> x,pair<int,int> y)
{
	double v1 = x.first;
	v1=ceil(v1/sqn);
	double v2 = y.first;
	v2=ceil(v2/sqn);
	if(v1==v2)
		return x.second<y.second;
	else
		return v1<v2;
}
int bit[SZ];
int l = SZ;

void bit_update(int i,int val)
{
  while(i<=l)
  {
    bit[i]=bit[i]+val;
    i=i+(i&(-i));
  }
}

int bit_summ(int a)
{
  int s=0;
  while(a>0)
  {
    s+=bit[a];
    a=a-(a&(-a));
  }
  return s;
}
int ans[SZ],num[SZ];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N,Q,l,r;
	cin>>N>>M;
	preprocess();
	sqn = sqrt(N);
	for(int i=1;i<=N;i++)
	{
		cin>>ar[i];
		vals[i-1] = ar[i];
	}
	sort(vals,vals+N);
	for(int i=1;i<=N;i++)
		ar[i] = lower_bound(vals,vals+N,ar[i]) - vals;
	for(int i=0;i<N;i++)
		vals[i]%=M;
	cin>>Q;
	vector<pair<pair<int,int>,int> > queries;
	for(int i=0;i<Q;i++)
	{
		cin>>l>>r;
		queries.push_back(make_pair(make_pair(l,r),i));
	}
	sort(queries.begin(),queries.end(),[&](pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
		return sub(a.first,b.first);
	});
	l=r=1;
	num[ar[1]]++;
	bit_update(ar[1]+1,1);
	update(0,N-1,ar[1],0,1,true);
	for(int i=0; i<queries.size(); i++)
	{
		pair<int,int> p = queries[i].first;
		int ix = queries[i].second,pos;
		while(l<p.first)
		{
			num[ar[l]]--;
			if(num[ar[l]]==0)
			{
				bit_update(ar[l]+1,-1);
				update(0,N-1,ar[l],0,0,false);
			}
			l++;
		}
		while(l>p.first)
		{
			l--;
			num[ar[l]]++;
			if(num[ar[l]]==1)
			{
				pos = bit_summ(ar[l]) + 1;
				bit_update(ar[l]+1,1);
				update(0,N-1,ar[l],0,pos,true);
			}
		}
		while(r<p.second)
		{
			r++;
			num[ar[r]]++;
			if(num[ar[r]]==1)
			{
				pos = bit_summ(ar[r]) + 1;
				bit_update(ar[r]+1,1);
				update(0,N-1,ar[r],0,pos,true);
			}
		}
		while(r>p.second)
		{
			num[ar[r]]--;
			if(num[ar[r]]==0)
			{
				bit_update(ar[r]+1,-1);
				update(0,N-1,ar[r],0,0,false);
			}
			r--;
		}
		ans[ix] = st[0][0];
	}
	for(int i=0; i<Q; i++)
		cout<<ans[i]<<"\n";
}