#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,SQ=320;
int n,m,a[N],bl,blo[N],cnt[N],sum[N],pow1[SQ+5],pow2[SQ+5],ans[N];
int nxt[N],pre[N],ed;
inline void insert(int x) 
{
	nxt[ed]=x;
	pre[x]=ed;
	ed=x;
}
inline void erase(int x)
{
	if(x^ed) 
	{
		nxt[pre[x]]=nxt[x];
		pre[nxt[x]]=pre[x];
	}
	else ed=pre[x];
	nxt[x]=pre[x]=0;
}
struct query{int l,r,P,id;}q[N];
inline void init(int P)
{
	pow1[0]=pow2[0]=1;for(int i=1;i<=SQ;i++) {pow1[i]=pow1[i-1]*2;pow1[i]=pow1[i]>=P?pow1[i]-P:pow1[i];}
	pow2[1]=pow1[SQ];for(int i=2;i<=SQ;i++) pow2[i]=1ll*pow2[i-1]*pow1[SQ]%P;
}
inline int gsm(int x,int P) {return 1ll*pow1[x%SQ]*pow2[x/SQ]%P;}
inline void add(int p)
{
	if(cnt[a[p]]) 
	{
		sum[cnt[a[p]]]-=a[p];
		if(!sum[cnt[a[p]]]) erase(cnt[a[p]]);		
	}
	cnt[a[p]]++;
	if(!sum[cnt[a[p]]]) insert(cnt[a[p]]);
	sum[cnt[a[p]]]+=a[p];
}
inline void del(int p)
{
	sum[cnt[a[p]]]-=a[p];
	if(!sum[cnt[a[p]]]) erase(cnt[a[p]]);
	cnt[a[p]]--;
	if(cnt[a[p]])
	{
		if(!sum[cnt[a[p]]]) insert(cnt[a[p]]);
		sum[cnt[a[p]]]+=a[p];
	}
}
inline int calc(int len,int P)
{
	int res=0,S=gsm(len,P);
	for(int i=nxt[0];i;i=nxt[i])
		res=res+1ll*sum[i]*(S-gsm(len-i,P)+P)%P,res=res>=P?res-P:res;
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);bl=sqrt(n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),blo[i]=(i-1)/bl+1;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].P),q[i].id=i;
	sort(q+1,q+1+m,[&](query a,query b){return blo[a.l]==blo[b.l]?a.r<b.r:a.l<b.l;});
	int pl=1,pr=0;
	for(int i=1;i<=m;i++) 
	{
		while(pl<q[i].l) del(pl++);
		while(pl>q[i].l) add(--pl);
		while(pr<q[i].r) add(++pr);
		while(pr>q[i].r) del(pr--);
		init(q[i].P);
		ans[q[i].id]=calc(q[i].r-q[i].l+1,q[i].P);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

也不知道为什么，有时候把 pow1[SQ+5] 和 pow2[SQ+5] 数组开成pow1[N]和pow2[N]也会RE