#include<iostream>
#include<algorithm>
#include<cmath>
#include<unordered_set>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
namespace Lan {
    inline string sread() {
        string s=" ";char e=getchar();
        while(e==' '||e=='\n')e=getchar();
        while(e!=' '&&e!='\n')s+=e,e=getchar();
        return s;
    }
    inline void swrite(string s){
        for(char e:s)putchar(e);
        printf("\n");
    }
    inline ll read() {
        ll x=0,y=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}
        while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
        return x*=y;
    }
    inline void write(ll x) {
        if(x<0){x=-x,putchar('-');}ll sta[35],top=0;
        do sta[top++]=x%10,x/=10;while(x);
        while(top)putchar(sta[--top]+'0');
    }
}using namespace Lan;
const int N=1e5+9;
const int B=1e3+9;
int a[N],c[N],sum[N];//数，数量，出现k次的和
int L[B],R[B],pos[N];
ll t1[N],t2[N];
ll ans[N];
int cur,mi;
unordered_set<int> st;
struct Q{
    int l,r,p,id;
    friend bool operator < (const Q &a,const Q &b){
        return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;
    }
}que[N];
inline void init(int mod){//处理sqrt(n)
    t1[0]=1;
    for(int i=1;i<=mi;i++){
        t1[i]=t1[i-1]*2%mod;
    }
    t2[0]=1;
    for(int i=1;i<=mi;i++){
        t2[i]=t2[i-1]*t1[mi]%mod;
    }
}
inline ll cqmi(int x,int mod){//O(1)询问
    return t1[x%mi]*t2[x/mi]%mod;
}
inline ll query(int l,int r,int p){
    ll res=0;
    for(auto &i : st){
        res+=sum[i]*(cqmi(r-l+1,p)-cqmi(r-l+1-i,p)+p)%p;
    }
    res%=p;
    return res;
}
inline void add(int pos){
    sum[c[a[pos]]]-=a[pos];
    if(!sum[c[a[pos]]]){
        st.erase(c[a[pos]]);
    }
    c[a[pos]]++;
    if(!sum[c[a[pos]]]){
        st.insert(c[a[pos]]);
    }
    sum[c[a[pos]]]+=a[pos];
}
inline void del(int pos){
    sum[c[a[pos]]]-=a[pos];
    if(!sum[c[a[pos]]]){
        st.erase(c[a[pos]]);
    }
    c[a[pos]]--;
    if(!sum[c[a[pos]]]){
        st.insert(c[a[pos]]);
    }
    sum[c[a[pos]]]+=a[pos]; 
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=m;i++){
        que[i].l=read(),que[i].r=read(),que[i].p=read();
        que[i].id=i;
    }
    mi=sqrt(n)+1;
    int blo=n/sqrt(m);
    int t=ceil(1.0*n/blo);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    R[t]=n;
    for(int i=1;i<=t;i++){
        for(int j=L[i];j<=R[i];j++){
            pos[j]=i;
        }
    }
    sort(que+1,que+1+m);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(que[i].l<l){
            add(--l);
        }
        while(que[i].l>l){
            del(l++);
        }
        while(que[i].r>r){
            add(++r);
        }
        while(que[i].r<r){
            del(r--);
        }
        init(que[i].p);
        ans[que[i].id]=query(que[i].l,que[i].r,que[i].p);
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}