rt，用了光速幂和根号分治，估计是细节错了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm> 
#define ll long long
#define getpow(x) (power2[x/k]*power[x%k]%mod)
using namespace std;
const int N=1e5;
const int K=320;
int n,m,k,a[N+5],pos[N+5],L[K+5],R[K+5];
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
int spc[N+5],spctot,spclst[K+5],cnt[N+5];
void init(){
	k=sqrt(N*1.0);
	int block=k;
	int num=N/block+(N%block>0);
	for(int i=1;i<=num;i++){
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+block;
	}
	R[num]=N;
	for(int i=1;i<=num;i++){
		for(int j=L[i];j<=R[i];j++){
			pos[j]=i;
		}
	}
}
struct Query{
	int l,r,p;
	int id;
	friend bool operator<(Query A,Query B){
		if(pos[A.l]==pos[B.l]){
			if(pos[A.l]&1){
				return A.r<B.r;
			}else{
				return A.r>B.r;
			}
		}else{
			return pos[A.l]<pos[B.l];
		}
	}
}q[N+5];
ll f[K+5],sum;
void add(int x){
	x=a[x];
	if(!spc[x]){
		f[cnt[x]]-=x;
	}
	if(!cnt[x]){
		sum+=x;
	}
	cnt[x]++;
	if(!spc[x]){
		f[cnt[x]]+=x;
	}
}
void sub(int x){
	x=a[x];
	if(!spc[x]){
		f[cnt[x]]-=x;
	}
	cnt[x]--;
	if(!spc[x]){
		f[cnt[x]]+=x;
	}
	if(!cnt[x]){
		sum-=x;
	}
}
ll ans[N+5],power[K+5],power2[K+5];
ll query(int len,ll mod){
	power[0]=1;
	for(int i=1;i<=k;i++){
		power[i]=power[i-1]*2%mod;
	}
	power2[0]=1;
	for(int i=1;i<=k;i++){
		power2[i]=power2[i-1]*power[k]%mod;
	}
	ll res=sum*(power2[len/k]*power[len%k]%mod)%mod;
	for(int i=1;i<=min(k,len);i++){
		res=(res-f[i]*(power2[(len-i)/k]*power[(len-i)%k]%mod)%mod+mod)%mod;
	}
	for(int i=1;i<=spctot;i++){
		int x=spclst[i];
		res=(res-(ll)(x)*(power2[(len-cnt[x])/k]*power[(len-cnt[x])%k]%mod)%mod+mod)%mod;
	}
	return res;
}
int main(){
	init();
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		cnt[a[i]]++;
	}
	for(int i=1;i<=N;i++){
		if(cnt[i]>k){
			spc[i]=1;
			spclst[++spctot]=i;
		}else{
			f[0]+=i;
		}
	}
	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=m;i++){
		q[i].l=read(),q[i].r=read(),q[i].p=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>q[i].l){
			add(--l);
		}
		while(r<q[i].r){
			add(++r);
		}
		while(l<q[i].l){
			sub(l++);
		}
		while(r>q[i].r){
			sub(r--);
		}
		ans[q[i].id]=query(r-l+1,q[i].p);
	}
	for(int i=1;i<=m;i++){
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}