#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read(){
    register int x=0;register char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48),ch=getchar_unlocked();}
    return x;
}
struct FastMod {
    unsigned long long b, m;
    FastMod(unsigned long long b) : b(b), m(((__int128(1) << 64) / b)) {}
    unsigned long long reduce(unsigned long long a) {
        unsigned long long q = (unsigned long long)((__int128(m) * a) >> 64);
        unsigned long long r = a - q * b;
        return r>=b?r-b:r;
    }
};
FastMod F(2);
inline void write(int x){
    if(!x){
        puts("0");
        return;
    }
    register int top=0,st[10];
    while(x){
        st[++top]=x%10;
        x/=10;
    }
    ++top;
    while(--top) putchar(st[top]+'0');
    putchar('\n');
    return;
}
const int N=1e5+1;
struct node{
    int l,r,p,id;
}que[N];
struct LINKED_LIST{
    struct Link{int pre,nxt;}lk[N];int cnt;
    LINKED_LIST(){cnt=0;}
    inline void insert(int x){
        lk[cnt].nxt=x;
        lk[x].pre=cnt;
        cnt=x;
    }
    inline void erase(int x){
        x^cnt?lk[lk[x].pre].nxt=lk[x].nxt,lk[lk[x].nxt].pre=lk[x].pre:cnt=lk[x].pre;
        lk[x].pre=lk[x].nxt=0;
    }
}vis;
int a[N],id[N],len,pd[N],ans[N],pow1[N],pow2[N];
inline bool cmp(node x,node y){
    return id[x.l]^id[y.l]?x.l<y.l:id[x.l]&1?x.r<y.r:x.r>y.r;
}
inline void prepare(int p){
    F = FastMod(p);
    register int i;
    for(i=1;i<=len;++i) pow1[i]=F.reduce(pow1[i-1]<<1ll);
    for(i=1;i<=len+1;++i) pow2[i]=F.reduce(1ll*pow2[i-1]*pow1[len]);
    return;
}
inline int work(int x,int p){
    return F.reduce(1ll*pow1[x%len]*pow2[x/len]);
}
inline void add(int x){
    !pd[a[x]]?vis.insert(a[x]),1:0;
    ++pd[a[x]];
    return;
}
inline void delet(int x){
    --pd[a[x]];
    !pd[a[x]]?vis.erase(a[x]),1:0;
    return;
}
inline int max(int x,int y){
    return x>y?x:y;
}
int main(){
    register int n=read(),m=read(),i,j,l,r,all;
    len=sqrt(n),pow1[0]=pow2[0]=1;
    for(i=1;i<=n;++i) a[i]=read();
    for(i=1;i<=m;++i){
        que[i].l=read(),que[i].r=read(),que[i].p=read(),que[i].id=i;
        id[que[i].l]=(que[i].l-1)/len+1;
    }
    sort(que+1,que+1+m,cmp);
    i=l=que[1].l,r=que[1].r;
    prepare(que[1].p);
    --i;
    while(++i<=r) add(i);
    all=r-l+1;
    for(j=vis.lk[0].nxt;j;j=vis.lk[j].nxt){
        ans[que[1].id]=F.reduce(ans[que[1].id]+F.reduce(F.reduce(1ll*j*work(all-pd[j],que[1].p))*(work(pd[j],que[1].p)-1)));
    }
    for(i=2;i<=m;++i){
        prepare(que[i].p);
        while(l>que[i].l) --l,add(l);
        while(r<que[i].r) ++r,add(r);
        while(r>que[i].r) delet(r),--r;
        while(l<que[i].l) delet(l),++l;
        all=r-l+1;
        for(j=vis.lk[0].nxt;j;j=vis.lk[j].nxt)
            ans[que[i].id]=F.reduce(ans[que[i].id]+F.reduce(F.reduce(1ll*j*work(all-pd[j],que[i].p))*(work(pd[j],que[i].p)-1)));
    }
    i=0;
    while(++i<=m) write(ans[i]);
    return 0;
}