求调QwQ，就WA了一个数据点QwQ

#include <iostream>
#include <algorithm>
#include <cmath>
#define N 100005
#define il inline
#define reg register
#define ll long long
using namespace std;
ll S;
ll a[N];
ll ans[N],cnt[N];
ll dp1[N],dp2[N];
struct node
{
	ll pre,next,s;
}nd[N];
struct question
{
	ll l,r,p,pos;
	il bool operator<(const question a)const
	{
		bool t((l-1)/S+1==(a.l-1)/S+1);
		return t?(r-1)/S+1<(a.r-1)/S+1:(l-1)/S+1<(a.l-1)/S+1;
	}
}q[N];
il void ins1(const ll x, const ll s)
{
	ll n=nd[x].next;
	nd[n].pre=x+1;
	nd[x].next=x+1;
	nd[x+1].s=s;
	nd[x+1].pre=x;
	nd[x+1].next=n;
}
il void ins2(const ll x, const ll s)
{
	ll p=nd[x].pre;
	nd[p].next=x-1;
	nd[x].pre=x-1;
	nd[x-1].s=s;
	nd[x-1].pre=p;
	nd[x-1].next=x;
}
il void rmv(const ll x)
{
	nd[nd[x].pre].next=nd[x].next;
	nd[nd[x].next].pre=nd[x].pre;
	nd[x].next=nd[x].pre=0;
}
il void add(const ll x)
{
	ll c=cnt[x];
	nd[c].s-=x;
	if(nd[c].next!=c+1)ins1(c,x);
	else nd[c+1].s+=x;
	if(!nd[c].s)rmv(c);
	cnt[x]++;
}
il void del(const ll x)
{
	ll c(cnt[x]);
	nd[c].s-=x;
	if(nd[c].pre!=c-1&&c>1)ins2(c,x);
	else nd[c-1].s+=x;
	if(!nd[c].s)rmv(c);
	cnt[x]--;
}
il ll qp(const ll x, const ll p){return 1*dp2[x/S]*dp1[x%S]%p;}
int main()
{
	ll n,m;
	ll l=1,r=0;
	cin>>n>>m;
	S=sqrt(n);
	for (reg ll i=1;i<=n;i++)cin>>a[i];
	for (reg ll i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r>>q[i].p;
		q[i].pos=i;
	}
	sort(q+1,q+m+1);
	for(reg ll i=1;i<=m;i++)
	{
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(r>q[i].r)del(a[r--]);
		while(l<q[i].l)del(a[l++]);
		dp1[0]=dp2[0]=1;
		for(reg ll j=1;j<=S;j++)
			dp1[j]=2*dp1[j-1]%q[i].p;
		for(reg ll j=1;j<=S;j++)
			dp2[j]=1*dp2[j-1]*dp1[S]%q[i].p;
		for(reg ll j=nd[0].next;j;j=nd[j].next)
			ans[q[i].pos]=(1*ans[q[i].pos]+1*nd[j].s*(qp(q[i].r-q[i].l+1,q[i].p)-qp(q[i].r-q[i].l+1-j,q[i].p))%q[i].p)%q[i].p;
		ans[q[i].pos]=(ans[q[i].pos]+q[i].p)%q[i].p;
	}
	for(reg ll i=1;i<=m;i++)
		cout<<ans[i]<<endl;
	return 0;
}