题解：
坑题搞了三天。
莫队+线段树。
还有一些和斐波那契数列有关的性质。
首先答案是$a_1f_1+a_2f_2+…+a_nf_n$，
考虑插进去一个元素对答案产生的影响。
比如插进去一个$a_0$，插进去之后会排到第$k$位。
那么答案是$a_1f_1+a_2f_2+…+a_0f_k+a_kf_{k+1}+…+a_nf_{n+1}$，
等于$ans0+a_0f_k+a_kf_{k-1}+…+a_nf_{n-1}$。
所以单点插入，区间加斐波那契数？
不可能的。
考虑用矩阵推出斐波那契数列。
其实不需要矩阵快速幂，存当前$a_i*f_i$和前一个数$a_i*f_{i-1}$即可，
比如我们存的是$(a,b)$，那么有
$(a,b)->(a+b,a)->(2a+b,a+b)->(3a+2b,2a+b)->(5a+3b,3a+2b)->……$
系数都是斐波那契数。
向前转移同理
$(a,b)->(b,a-b)->(a-b,-a+2b)->(-a+2b,2a-3b)->……$
这个系数可以和斐波那契数列一起求，转移也很好推。
线段树单点插入时要一起搞事情，取模要少取，不然会$T$的很惨。
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = ;
template<typename T>
inline void read(T&x)
{
T f = ,c = ;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}
x = f*c;
}
int n,qq,w[N],to[N],m=,B=;
int MOD,f[N],g[N],ans[N];
void Mod(int&x){if(x>=MOD)x-=MOD;}
void init()
{
if(MOD==)return ;
f[]=f[]=;
for(int i=;i<=n+;i++)
Mod(f[i]=f[i-]+f[i-]);
g[]=,g[]=MOD-;
for(int i=;i<=n+;i++)
Mod(g[i]=g[i-]-g[i-]+MOD);
}
struct Pair
{
int x,y;
Pair(){}
Pair(int x,int y):x(x),y(y){}
}p[N];
bool cmp(Pair a,Pair b){return a.x<b.x;}
struct Q
{
int l,r,id;
Q(){}
Q(int l,int r,int i):l(l),r(r),id(i){}
}q[N];
bool CMP(Q a,Q b){return (a.l/B)==(b.l/B)?(a.r<b.r):(a.l<b.l);}
struct segtree
{
int siz[N<<],tag[N<<];
int c[N<<][];
void update(int u)
{
siz[u] = siz[u<<]+siz[u<<|];
Mod(c[u][] = c[u<<][]+c[u<<|][]);
Mod(c[u][] = c[u<<][]+c[u<<|][]);
}
void add(int u,int k)
{
tag[u] += k;
int a = c[u][],b = c[u][];
if(k>)
{
(c[u][] = a*f[k+]+b*f[k])%=MOD;
(c[u][] = a*f[k]+b*f[k-])%=MOD;
}else if(k<)
{
k = -k;
(c[u][] = a*g[k-]+b*g[k])%=MOD;
(c[u][] = a*g[k]+b*g[k+])%=MOD;
}
}
void pushdown(int u)
{
if(tag[u])
{
add(u<<,tag[u]);
add(u<<|,tag[u]);
tag[u] = ;
}
}
void insert(int l,int r,int u,int qx,int k,int d)
{
if(l==r)
{
if(k==-)c[u][]=c[u][]=,siz[u] = ;
else c[u][] = f[k]*to[l]%MOD,c[u][] = f[k-]*to[l]%MOD,siz[u] = ;
return ;
}
pushdown(u);
int mid = (l+r)>>;
if(qx<=mid)insert(l,mid,u<<,qx,k,d),add(u<<|,d);
else insert(mid+,r,u<<|,qx,k+(k!=-)*siz[u<<],d);
update(u);
}
}tr;
int vis[N];
inline void push(int x)
{
if(!x)return ;
if(!vis[x])tr.insert(,m,,x,,);
vis[x]++;
}
inline void pull(int x)
{
if(!x)return ;
vis[x]--;
if(!vis[x])tr.insert(,m,,x,-,-);
}
int main()
{
// freopen("tt.in","r",stdin);
read(n),read(MOD);
init();
for(int a,i=;i<=n;i++)
read(a),p[i]=Pair(a,i);
sort(p+,p++n,cmp);
for(int las = 0x3f3f3f3f,i=;i<=n;i++)
{
if(las != p[i].x)
{
las = p[i].x;
to[++m] = las%MOD;
}
w[p[i].y] = m;
}
read(qq);
for(int l,r,i=;i<=qq;i++)
{
read(l),read(r);
q[i]=Q(l,r,i);
}
sort(q+,q++qq,CMP);
int L = ,R = ;
for(int i=;i<=qq;i++)
{
while(R<q[i].r)push(w[++R]);
while(R>q[i].r)pull(w[R--]);
while(L<q[i].l)pull(w[L++]);
while(L>q[i].l)push(w[--L]);
ans[q[i].id]=tr.c[][];
}
for(int i=;i<=qq;i++)
printf("%d\n",ans[i]);
return ;
}