#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
struct istream{
    char buf[23333333],*s;
    inline e istream&operator>>(int&d){
        d=0;
        for(;!isdigit(*s);++s);
        while(isdigit(*s)) d=(d<<3)+(d<<1)+(*s++^'0');
        return*this;
    }
}cin;
typedef long long ll;
const int size=317;
const int N=100010;
struct node{
    int l,r,mod,id;
}q[N];
int n,m;
std::unordered_set<int> qwq;
int fk[N],a[N],cnt[N],awa[N],p1[N]={1},p2[N]={1};
ll ans[N];
inline bool cmp(node a,node b)
{
    return (fk[a.l]^fk[b.l])?fk[a.l]<fk[b.l]:fk[a.l]&1?a.r<b.r:a.r>b.r;
}
inline void add(int i)//位置
{
    register int x=cnt[i];
    if(x){/*如果cnt包含x[i]*/awa[x]-=i;/*减掉*/if(awa[x]==0) qwq.erase(x);/*如果元素不存在了(被删掉了为0)，则把它从表里删去*/}
    ++cnt[i],x=cnt[i];
    if(!awa[x])/*如果不包含x*/ qwq.insert(x);
    awa[x]+=i;
}
inline void del(int i)//位置
{
    register int x=cnt[i];
    awa[x]-=i;
    if(!awa[x])/*如果不包含x*/ qwq.erase(x);
    --cnt[i],x=cnt[i];
    if(x){/*如果cnt包含x[i]*/if(awa[x]==0) qwq.insert(x);/*如果元素不存在了则把它加入表里*/awa[x]+=i;/*加上*/}
}
inline void work(int i){register int l=1,r=0;while(l<q[i].l) del(a[l++]);while(l>q[i].l) add(a[--l]);while(r<q[i].r) add(a[++r]);while(r>q[i].r) del(a[r--]);}
inline ll pow(int i,int qaq){
    return 1ll*p1[i%size]*p2[i/size]%qaq;
}
inline ll iee(int l,int r,int qaq)
{
    ll ans=0;
    ll S=pow(r-l+1,qaq);
    std::unordered_set <int>::iterator it;
    for(it=qwq.begin();it!=qwq.end();++it) ans=(ans+awa[*it]*(S-pow(r-l+1-*it,qaq)+qaq)%qaq)%qaq;
    ans%=qaq;
    return ans;
}
int main(){
    cin>>n,cin>>m;
    for(register int i=1;i<=n;i++) fk[i]=(i-1)/size+1;
    for(register int i=1;i<=n;++i) cin>>a[i];
    for(register int i=1;i<=m;++i){cin>>q[i].l,cin>>q[i].r,cin>>q[i].mod;q[i].id=i;}
    std::sort(q+1,q+1+m,cmp);
    for(register int i=1;i<=m;++i){
        work(i);
        for(register int j=1;j<=size;++j) p1[j]=1ll*(p1[j-1]<<1)%q[i].mod;
        p2[1]=p1[size];
        for(register int j=2;j<=size;++j) p2[j]=1ll*p2[j-1]*p2[1]%q[i].mod;
        ans[q[i].id]=iee(q[i].l,q[i].r,q[i].mod);
    }
    for(register int i=1;i<=m;++i) std::cout<<ans[i]<<std::endl;
    return 0;
}