交了30多遍了，第九个点一直比时限多了一点，卡不动了/kel

#pragma GCC target( "avx" )
#pragma GCC optimize( 3 )
#pragma GCC optimize( "Ofast" )
#pragma GCC optimize( "inline" )
#pragma GCC optimize( "-fgcse" )
#pragma GCC optimize( "-fgcse-lm" )
#pragma GCC optimize( "-fipa-sra" )
#pragma GCC optimize( "-ftree-pre" )
#pragma GCC optimize( "-ftree-vrp" )
#pragma GCC optimize( "-fpeephole2" )
#pragma GCC optimize( "-ffast-math" )
#pragma GCC optimize( "-fsched-spec" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC optimize( "-falign-jumps" )
#pragma GCC optimize( "-falign-loops" )
#pragma GCC optimize( "-falign-labels" )
#pragma GCC optimize( "-fdevirtualize" )
#pragma GCC optimize( "-fcaller-saves" )
#pragma GCC optimize( "-fcrossjumping" )
#pragma GCC optimize( "-fthread-jumps" )
#pragma GCC optimize( "-funroll-loops" )
#pragma GCC optimize( "-fwhole-program" )
#pragma GCC optimize( "-freorder-blocks" )
#pragma GCC optimize( "-fschedule-insns" )
#pragma GCC optimize( "inline-functions" )
#pragma GCC optimize( "-ftree-tail-merge" )
#pragma GCC optimize( "-fschedule-insns2" )
#pragma GCC optimize( "-fstrict-aliasing" )
#pragma GCC optimize( "-fstrict-overflow" )
#pragma GCC optimize( "-falign-functions" )
#pragma GCC optimize( "-fcse-skip-blocks" )
#pragma GCC optimize( "-fcse-follow-jumps" )
#pragma GCC optimize( "-fsched-interblock" )
#pragma GCC optimize( "-fpartial-inlining" )
#pragma GCC optimize( "no-stack-protector" )
#pragma GCC optimize( "-freorder-functions" )
#pragma GCC optimize( "-findirect-inlining" )
#pragma GCC optimize( "-fhoist-adjacent-loads" )
#pragma GCC optimize( "-frerun-cse-after-loop" )
#pragma GCC optimize( "inline-small-functions" )
#pragma GCC optimize( "-finline-small-functions" )
#pragma GCC optimize( "-ftree-switch-conversion" )
#pragma GCC optimize( "-foptimize-sibling-calls" )
#pragma GCC optimize( "-fexpensive-optimizations" )
#pragma GCC optimize( "-funsafe-loop-optimizations" )
#pragma GCC optimize( "inline-functions-called-once" )
#pragma GCC optimize( "-fdelete-null-pointer-checks" )
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<vector>
#include<algorithm>
#define ll long long
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,block,tot,top,tail,tool,head;
int a[maxn],cnt[maxn],st[maxn],id[maxn];
ll _pow[maxn],bpow[maxn],ans[maxn],sum;
struct question
{
	int l,r,p,id;
}q[maxn];
struct lin
{
	int last,next,cnt;
	ll val;
}link[maxn];

inline bool cmp(const question x,const question y)
{
	return (x.l/block)^(y.l/block)?(x.l/block)<(y.l/block):(((x.l/block)&1)?x.r<y.r:x.r>y.r);
}

inline int read()
{
	int num;
	char c;
	while((c=getchar())<'0'||c>'9');
	num=c-'0';
	while((c=getchar())>='0'&&c<='9')
		num=(num<<1)+(num<<3)+c-'0';
	return num;
}

int buf[15];
inline void writeint(int i){
	int p= 0;
	if(!i) buf[p++]=0;
	while(i)
	{
		buf[p++]=i%10;
		i/=10;
	}
	for(register int j=p-1;j>=0;--j)putchar('0'+buf[j]);
	puts("");
}

inline int newnode()
{
	if(top)return st[top--];
	return ++tot;
}

inline void recycle(int x)
{
	st[++top]=x;
	link[x].val=link[x].next=0;
}

inline void solve(int x,int val)
{
	link[id[cnt[a[x]]]].val-=a[x];
	if(!link[id[cnt[a[x]]]].val&&id[cnt[a[x]]])
	{
		int t=id[cnt[a[x]]];
		id[cnt[a[x]]]=0;
		link[link[t].last].next=link[t].next;
		link[link[t].next].last=link[t].last;
		if(!link[t].next)tail=link[t].last;
		recycle(t);
	}
	cnt[a[x]]+=val;
	if(cnt[a[x]])
	{
		int t=id[cnt[a[x]]];
		if(!t)
		{
			t=id[cnt[a[x]]]=newnode();
			link[tail].next=t;
			link[t].last=tail;
			tail=t;
			link[t].cnt=cnt[a[x]];
		}
		link[t].val+=a[x];
	}
}

signed main(void)
{
	n=read(),m=read();
	block=n/sqrt(n*2.0/3.0);
	for(register int i=1;i<=n;++i)a[i]=read();
	for(register 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+1+m,cmp);
	int l=1,r=0;
	_pow[0]=bpow[0]=1; 
	for(register int i=1;i<=m;++i)
	{
		int len=q[i].r-q[i].l+1;
		int sq=sqrt(len);
		sum=0;
		for(register int j=1;j<=sq;++j)_pow[j]=_pow[j-1]*2%q[i].p;
		for(register int j=1;j*sq<=len;++j)bpow[j]=bpow[j-1]*_pow[sq]%q[i].p;
		while(l<q[i].l)
			solve(l++,-1);
		while(l>q[i].l)
			solve(--l,1);
		while(r<q[i].r)
			solve(++r,1);
		while(r>q[i].r)
			solve(r--,-1);
		ans[q[i].id]=sum%q[i].p*(bpow[len/sq]*_pow[len%sq]%q[i].p)%q[i].p;
		for(register int j=link[0].next;j;j=link[j].next)
		{
			int t=len-link[j].cnt;
			ans[q[i].id]=(ans[q[i].id]-link[j].val*((bpow[t/sq]*_pow[t%sq])%q[i].p)%q[i].p+q[i].p)%q[i].p;
			sum+=link[j].val;
		}
		sum%=q[i].p;
		ans[q[i].id]=(ans[q[i].id]+sum*(bpow[len/sq]*_pow[len%sq]%q[i].p)%q[i].p)%q[i].p;
	}
	for(register int i=1;i<=m;++i)writeint(ans[i]);
	return 0;
}

求大佬帮卡卡常/kel