RT...

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt[1000005],a[1000005],block,num[1000005],ans[1000005],sum[1000005],l=1,r;
int p1[1000005],p2[1000005],total;
struct node {
	int l,r,mod,p,len;
} q[1000005];
struct list {
	int pre,nxt;
} L[1000005];
void add(int x) {
	L[total].nxt=x;
	L[x].pre=total;
	total=x;
}
void det(int x) {
	if(x!=total) {
		L[L[x].pre].nxt=L[x].nxt;
		L[L[x].nxt].pre=L[x].pre;
	} else total=L[x].pre;
}
bool cmp(node x,node y) {
	if(num[x.l]!=num[y.l])return x.l<y.l;
	return x.r<y.r;
}
void power(int mod) {
	p1[0]=p2[0]=1;
	for(int i=1; i<=block; i++)p1[i]=(p1[i-1]*2)%mod;
	for(int i=1; i<=block; i++)p2[i]=(p2[i-1]*p1[block])%mod;
}
int query(int x,int mod) {
	return (p1[x%block]*p2[x/block])%mod;
}
void update(int p,int opt) {
	sum[cnt[a[p]]]-=a[p];
	if(!sum[cnt[a[p]]])det(cnt[a[p]]);
	cnt[a[p]]+=opt;
	if(!sum[cnt[a[p]]])add(cnt[a[p]]);
	sum[cnt[a[p]]]+=a[p];
}
signed main() {
	scanf("%lld%lld",&n,&m);
	block=sqrt(n);
	for(int i=1; i<=n; i++)scanf("%lld",&a[i]),num[i]=(i/block)+(i%block!=0);
	for(int i=1; i<=m; i++) {
		scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].mod);
		q[i].p=i,q[i].len=q[i].r-q[i].l+1;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1; i<=m; i++) {
		power(q[i].mod);
		while(l>q[i].l)l--,update(l,1);
		while(l<q[i].l)update(l,-1),l++;
		while(r<q[i].r)r++,update(r,1);
		while(r>q[i].r)update(r,-1),r--;
		int p=q[i].p;
		for(int j=L[0].nxt; j; j=L[j].nxt) {
			int res=(sum[j]*(query(q[i].len,q[i].mod)-query(q[i].len-j,q[i].mod)))%q[i].mod;
			res=(res+q[i].mod)%q[i].mod;
			ans[p]+=res;
			ans[p]%=q[i].mod;
		}
	}
	for(int i=1; i<=m; i++)printf("%lld\n",ans[i]);
}