#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=114514,B=300,MAX=1e5;	//B 表示块长 MAX 是值域最大值  
int n,q;
int a[N],acx[N]; // a 的出现情况 
int aclass[N];	//a 中每一个数是否用链表存储  
int head;	//表示链表开始位置 
int lst[N],nxt[N];	//链表的前后两个元素  

int ap[N];	//所有的数的出现情况 
int sap[B+15];	//sap 专门统计较小数的情况  
struct node{
	int l,r,mod,id;
}q1[N];
int include13_fAKe[N];	//所有的最终的答案  
bool cmp(node a,node b){
	int ax=a.l/B,bx=b.l/B;
	if(ax!=bx)	return ax<bx;
	if(ax%2)	return a.r<b.r;
	else	return a.r>b.r;
}
inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar(); 
	}
	return a*b;
}
inline void write(int x){
	if(x<0){
		putchar('-'),x=-x;
	}
	if(x>=10)	write(x/10);
	putchar(x%10+'0');
}
inline void write1(int x){
	write(x),putchar(' ');
} 
inline void write2(int x){
	write(x),putchar('\n');
}
int pow2[N];	//记录 2 的次幂  
void init(int mod){
	//这里的模数是不确定的 
	pow2[0]=1;
	for(int i=1;i<=B;i++){
		pow2[i]=pow2[i-1]*2;
//		cout<<i<<' '<<pow2[i]<<endl;
	} 
	for(int i=B;i<=MAX;i+=B){
		pow2[i]=pow2[i-B]*pow2[B];
//		cout<<i<<' '<<pow2[i]<<endl;
	}
} 
void add(int now){
	//现在要加入的数 
	int sum=a[now];	//目前的位置 
	//考虑如果是轻元素的处理方案 
	if(!aclass[sum]){
		//代表是轻元素 
		//出现次数 +1 
		int lst=ap[sum];	//原来出现的情况  
		if(lst!=0){
			sap[lst]-=sum;
		} 
		sap[lst+1]+=sum;	//sap[i] 就是出现次数为 i 的数的总和  
	}  
	ap[sum]++;	//最后的计算  
}
void del(int now){
	int sum=a[now];
	if(!aclass[sum]){
		int lst=ap[sum];
		sap[lst]-=sum;
		if(lst!=1)	sap[lst-1]+=sum;
	}
	ap[sum]--;
} 
signed main(){
//	init(114514);
	n=read(),q=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),acx[a[i]]++;	//统计下一次出现的位置  
	}
	for(int i=1;i<=MAX;i++){
		if(acx[i]>=B){
			head=i;
			aclass[i]=1;
			break; 
		}
	} 
	int lst1=head;//后来才有的改变  
	for(int i=head+1;i<=MAX;i++){
		//这里默认已经跳过了表头  
		if(acx[i]>=B){
			lst[i]=lst1;
			nxt[lst1]=i;
			lst1=i;	//传统的链表维护方法 实际上链表建好之后就是静态的  
			aclass[i]=1; 
		}  
	}//相当于两个循环跑了一整遍  
//	for(int i=1;i<=MAX;i++){
//		if(aclass[i]){
//			cout<<'#'<<i<<' '<<lst[i]<<" "<<nxt[i]<<endl;
//		}
//	}
	for(int i=1;i<=q;i++){
		q1[i].l=read(),q1[i].r=read(),q1[i].mod=read(),q1[i].id=i;
	}
	sort(q1+1,q1+q+1,cmp);
	int l=1,r=0;	//如果不想处理 0 位置的情况可以这么写  
//	cout<<endl;
	for(int i=1;i<=q;i++){
		int include13=0;	//这里的局部答案  
		int mod=q1[i].mod;
//		cout<<'#'<<q1[i].id<<endl;
		//l-- r++ l++ r-- 
		init(mod);
		while(l>q1[i].l){
			l--,add(l);
		} 
		while(r<q1[i].r){
			r++,add(r); 
		}
		while(l<q1[i].l){
			del(l),l++;
		}
		while(r>q1[i].r){
			del(r),r--;
		}
		int sum1=r-l+1;	//全局的数的个数  
		for(int i=head;i;i=nxt[i]){
			int now=i;
			int all1=sum1,nall1=sum1-ap[i];
			int all=pow2[sum1/B*B]*pow2[sum1%B]%mod;
			int nall=pow2[nall1/B*B]*pow2[nall1%B]%mod; 
			int c=all-nall+mod;
			c%=mod;
//			cout<<now<<' '<<c<<endl;
			include13+=now*c;	//出现次数较多的数的处理方法  
			include13%=mod;
//			cout<<include13<<' ';
		}
//		cout<<"第一次巡回完成"<<endl;
//		cout<<include13<<endl;
		for(int i=1;i<=B;i++){
			//统计轻元素 
			//这里的 i 是出现次数 
			int now=sap[i];
//			int all=pow2[sum1],nall=pow2[sum1-i];
			int all1=sum1,nall1=sum1-i;
			int all=pow2[sum1/B*B]*pow2[sum1%B];
			int nall=pow2[nall1/B*B]*pow2[nall1%B]; 
//			cout<<'%'<<all1<<' '<<nall1<<endl;
//			cout<<'%'<<all<<" "<<nall<<endl;
//			int c=(all-nall+mod)%mod;
			int c=(all-nall+mod)%mod;
			include13+=now*c; 
//			cout<<"^"<<now<<' '<<c<<endl;
			include13%=mod;
//			cout<<'#'<<include13<<endl;
		} 
//		cout<<"第二次巡回完成"<<endl; 
//		cout<<include13<<endl;
//		cout<<endl;
		include13_fAKe[q1[i].id]=include13;
//		cout<<"谭总的世界-031"<<" "<<l<<' '<<r<<' '<<include13<<endl; 
	}
	for(int i=1;i<=q;i++){
		write2(include13_fAKe[i]);
	}
	putchar('\n');
	return 0;
} //纵使日薄西山，即使看不到未来，此时此刻的光辉，盼君勿忘。