#include <bits/stdc++.h>
#define Arknights return
#define AK 0
#define IOI ;
#define ll long long
#define ld long double
#define ull unsigned ll
#define lll __int128
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppp pair<pii,pii>
#define deb cerr<<"Arknights AK IOI\n"
#define tostring(a) #a
#define cono(a,b) a##b
#define psa(i) (i=-~(i))
#define range(i) (-~(i))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

inline int read()
{
	int s=0;int w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^'0'),ch=getchar();
	return s*w;
}
void IO()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
const int N=1e5+10,M=1e3+10;
const ll MAXMOD=1e13+37;
int n,block_len,siz,a[N],len,t,block[N],cnt[N];
ll cur,lg[N],ans[N];

struct queuelist
{
	struct node
	{
		int pre,ne;
		node(int a=0,int b=0):pre(a),ne(b){}
	}lst[N];
	int tot;
	queuelist(int a=0):tot(a){}
	
	void insert(int x)
	{
		lst[tot].ne=x;
		lst[x].pre=tot;
		tot=x;
	}
	
	void remove(int x)
	{
		if(x==tot)
		{
			lst[lst[x].pre].ne=0;
			tot=lst[x].pre;
		}
		else
		{
			lst[lst[x].pre].ne=lst[x].ne;
			lst[lst[x].ne].pre=lst[x].pre;
		}
		lst[x]=node();
	}
}qouyu;
struct Query
{
	int l,r,p,idx;
	bool operator <(const Query p)const
	{
		if(block[l] xor block[p.l])return l<p.l;
		if(block[l]&1)return r<p.r;
		return r>p.r;
	}
}q[N];
namespace qpow
{
	int pow1[M],pow2[M];
	inline void initpow(int mod)
	{
		pow1[0]=pow2[0]=1;
		for(int i=1;i<=siz+5;++i)pow1[i]=(ll)(pow1[i-1])*2%mod;
		for(int i=1;i<=siz+5;++i)pow2[i]=(ll)(pow2[i-1])*pow1[siz]%mod;
	}
	inline int calc(int x,int mod)
	{
		return (ll)(pow1[x%siz])*pow2[x/siz]%mod;
	}
}
inline void build()
{
	block_len=pow(n,2.0/3.0);
	for(int i=1;i<=block_len;++i)block[i]=1;
	for(int i=block_len+1;i<=n;++i)
		block[i]=block[i-block_len]+1;
}
//inline void add(int pnt,ll MOD=MAXMOD)
//{
//	cur<<=1;
//	if(!cnt[a[pnt]])cur=(cur+lg[len]*a[pnt])%MOD;
//	else cur=(cur+lg[len-cnt[a[pnt]]]*a[pnt])%MOD;
//	psa(cnt[a[pnt]]);psa(len);
//}
//inline void del(int pnt,ll MOD=MAXMOD)
//{
//	--cnt[a[pnt]];--len;
//	if(!cnt[a[pnt]])cur-=lg[len]*a[pnt];
//	else cur-=lg[len-cnt[a[pnt]]]*a[pnt];
//	if(cur<=0)cur+=MOD;cur>>=1;
//}
inline void add(int pnt)
{
	if(!cnt[a[pnt]])qouyu.insert(a[pnt]);
	++cnt[a[pnt]];
}
inline void del(int pnt)
{
	--cnt[a[pnt]];
	if(!cnt[a[pnt]])qouyu.remove(a[pnt]);
}
int main()
{
	n=read(),t=read();
	build();lg[0]=1;siz=sqrt(n);
	for(int i=1;i<=n;++i)a[i]=read();
//		,lg[i]=(lg[i-1]<<1)%MAXMOD;
	for(int i=1,l,r,p;i<=t;++i)
	{
		l=read(),r=read(),p=read();
		q[i]=(Query){l,r,p,i};
	}
	sort(q+1,q+1+t);
//	deb;
	for(int l=1,r=0,i=1;i<=t;++i)
	{
		qpow::initpow(q[i].p);
		while(l>q[i].l)add(--l);
//		cerr<<cur<<endl;
		while(l<q[i].l)del(l++);
//		cerr<<cur<<endl;
		while(r>q[i].r)del(r--);
//		cerr<<cur<<endl;
		while(r<q[i].r)add(++r);
//		cerr<<cur<<endl;
		for(int it=qouyu.lst[0].ne;it;it=qouyu.lst[it].ne)
		{
			ll tmp1=qpow::calc(r-l+1,q[i].p);
			ll tmp2=qpow::calc(r-l+1-cnt[it],q[i].p);
			if(tmp1<tmp2)tmp1+=q[i].p;
			ans[q[i].idx]+=(tmp1-tmp2)*it;
		}
		ans[q[i].idx]=ans[q[i].idx]%q[i].p;
//		cerr<<q[i].idx<<": l:"<<q[i].l<<" r:"<<q[i].r<<" cur:"<<cur<<endl;
	}
	for(int i=1;i<=t;++i)printf("%d\n",ans[i]);
	Arknights AK IOI
}

光速幂，链表，莫队，感觉没问题（）