94pts 难以通过

#include<bits/stdc++.h>
#define rint register int
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+5;
template <class T>
inline void read(T &res){
	char c;bool f=0;
	while(!isdigit(c=getchar())) if(c=='-') f=1;
	res=(c^48);
	while(isdigit(c=getchar())) res=(res<<1)+(res<<3)+(c^48);
	if(f) res=~res+1;
}
template <class T>
inline void Print(T x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) Print(x/10);
    putchar(x%10+48);
}
int n,m,B,a[N],b[N];
struct Query{
	int id,l,r; ll p;
	bool operator < (const Query &tmp) const { return l/B==tmp.l/B?r<tmp.r:l/B<tmp.l/B;} 
}q[N];
struct Node{
	int pre,nxt;
}nod[N];
int tot=0;
void insert(int x){
	nod[tot].nxt=x;
	nod[x].pre=tot;
	tot=x;
}
void erase(int x){
	if(x!=tot){
		nod[nod[x].pre].nxt=nod[x].nxt;
		nod[nod[x].nxt].pre=nod[x].pre;
	}
	else{
		nod[nod[x].pre].nxt=0;
		tot=nod[x].pre;
	} 
	nod[x]=(Node){0,0};
}
int cnt[N];
ll sum[N],ans[N];
inline void add(int x){ 
	if(cnt[x]){ 
		sum[cnt[x]]-=x;
		if(!sum[cnt[x]]) erase(cnt[x]);
	}
	cnt[x]++;
	if(!sum[cnt[x]]) insert(cnt[x]);
	sum[cnt[x]]+=x;
}
inline void del(int x){ 
	sum[cnt[x]]-=x;
	if(!sum[cnt[x]]) erase(cnt[x]);
	cnt[x]--;
	if(cnt[x]){ 
		if(!sum[cnt[x]]) insert(cnt[x]);
		sum[cnt[x]]+=x;
	}
} 
int Size;
ll pow1[N],pow2[N];
ll calc(ll x,ll mod){return (pow1[x%Size]*pow2[x/Size])%mod;} 
void solve(){
	int l=1,r=0;
	sort(q+1,q+m+1);
	For(i,1,m){ 
		const Query &que=q[i];
		const ll mod=q[i].p;
		while(l>que.l) add(a[--l]);
		while(r<que.r) add(a[++r]);
		while(l<que.l) del(a[l++]);
		while(r>que.r) del(a[r--]);
		int t=r-l+1; 
		
		pow1[0]=pow2[0]=1;
		for(int i=1;i<=Size;i++) pow1[i]=pow1[i-1]*2%mod;
		for(int i=1;i<=Size;i++) pow2[i]=pow2[i-1]*pow1[Size]%mod;
		
		for(int j=nod[0].nxt;j;j=nod[j].nxt){ 
			ll a1=calc(t,mod), a2=calc(t-j,mod);
			ans[que.id]=(ans[que.id]+sum[j]*(a1-a2+mod)%mod)%mod;
		}
//		ans[que.id]=(ans[que.id]%mod+mod)%mod;
	}
}
signed main(){
	read(n),read(m); 
	B=Size=320; 
	For(i,1,n) read(a[i]);
	For(i,1,m){ 
		int l,r;ll p; read(l),read(r),read(p);
		q[i]=(Query){i,l,r,p};
	}
	solve();
	For(i,1,m) Print(ans[i]),putchar('\n');
	return 0;
} 

#9总是挂 记录