#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int n, m, a[N], fac[N], fac2[N];
int blk, cnt[N], ans[N];
int sum[N], pre[N], nxt[N], tot;//链表 
struct query{
	int l, r, p, id;
	bool operator < (const query &p) const {
		if(l / blk != p.l / blk)
			return l < p.l;
		return r < p.r;
	}
} q[N];

void insert(int k){//插入了一个出现次数为 k 的节点 
	nxt[tot] = k, pre[k] = tot;
	tot = k;
}

void delet(int k){//删除出现次数为 k 的节点 
	if(k != tot){
		pre[nxt[k]] = pre[k];
		nxt[pre[k]] = nxt[k];
	}
	else{
		nxt[pre[k]] = 0;
		tot = pre[k];
	}
	pre[k] = nxt[k] = 0;
}

void add(int x){
	int v = a[x];
	sum[cnt[v]] -= v;
	if(!sum[cnt[v]])//没了 
		delet(cnt[v]);//再见 
	++cnt[v];
	if(!sum[cnt[v]])
		insert(cnt[v]);
	sum[cnt[v]] += v;
}

void del(int x){
	int v = a[x];
	sum[cnt[v]] -= v;
	if(!sum[cnt[v]])
		delet(cnt[v]);
	--cnt[v];
	if(!sum[cnt[v]])
		insert(cnt[v]);
	sum[cnt[v]] += v;
}

int exp(int x, int p){
	return (fac2[x / blk] * fac[x % blk] % p + p) % p;
}

main(){
	scanf("%lld%lld", &n, &m);
	for(int i=1;i<=n;i++)
		scanf("%lld", &a[i]);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].p), q[i].id = i;
	blk = sqrt(m);
	sort(q + 1, q + 1 + m);
	int l = 1, r = 0;
	for(int i=1;i<=m;i++){
		while(l < q[i].l)
			del(l++);
		while(r > q[i].r)
			del(r--);
		while(l > q[i].l)
			add(--l);
		while(r < q[i].r)
			add(++r);
		fac[0] = fac2[0] = 1;
		int p = q[i].p;
		for(int j=1;j<=blk+2;j++)
			fac[j] = fac[j - 1] * 2ll % p;
		for(int j=1;j<=blk+2;j++)
			fac2[j] = fac2[j - 1] * fac[blk] % p;
		for(int j=nxt[0];j;j=nxt[j]){
			int tol = exp(r - l + 1, p);
			int tol2 = exp(r - l + 1 - j, p);
			int res = ((tol - tol2) * sum[j] % p + p) % p;
			ans[q[i].id] = ((ans[q[i].id] + res) % p + p) % p;
		}
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n", ans[i]);
	return 0;
}