#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize(3)

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int >
const int N = 1e5+9;
int n,q,a[N],A[N],num,cnt;
vi b[N];
map<vi ,int >mp;
int rt[N];
struct seg{int ch[2],sum;}t[N*70];
void pushup(int c){
    t[c].sum=t[t[c].ch[0]].sum+t[t[c].ch[1]].sum;return ;
}
void modify(int &c,int l,int r,int x,int y){
    if(!c) c=++cnt;
    if(l==r){t[c].sum+=y;return ;}
    int mid=(l+r)>>1;
    if(x<=mid) modify(t[c].ch[0],l,mid,x,y);
    if(x>mid) modify(t[c].ch[1],mid+1,r,x,y);
    pushup(c);return ;
}
int query(int c,int l,int r,int x,int y){
    if(!c) return 0;
    if(x<=l&&r<=y) return t[c].sum;
    int mid=(l+r)>>1,ans=0;
    if(x<=mid) ans+=query(t[c].ch[0],l,mid,x,y);
    if(y>mid) ans+=query(t[c].ch[1],mid+1,r,x,y);
    return ans;
}
int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}
struct qq{int l,r,x,id,ans;}Q[N];
bool cmp(qq x,qq y){return x.r<y.r;}
#define pi pair<int ,int >
#define fi first
#define se second
#define mcp make_pair
vector<pi >p[N];
int que(vi c,int l,int r){
    if(l==r) return l;
    int ans=0,mid=(l+r)>>1;
    for(int i=0;i<c.size();i++) ans+=t[t[c[i]].ch[1]].sum;
    if(ans>0){  
        for(int i=0;i<c.size();i++) c[i]=t[c[i]].ch[1];
        return que(c,mid+1,r);
    }
    for(int i=0;i<c.size();i++) c[i]=t[c[i]].ch[0];
    return que(c,l,mid);
}
bool cmpp(qq x,qq y){return x.id<y.id;}

int main(){
    num=0,cnt=0;vi v;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);A[i]=a[i];
        for(int j=2;j*j<=a[i];j++)
            if(a[i]%j==0){
                while(a[i]%j==0) a[i]/=j;
                b[i].push_back(j);
            }
        if(a[i]!=1) b[i].push_back(a[i]);
        for(int k=0;k<(1<<(int)b[i].size());k++){
            v.clear();
            for(int j=0;j<b[i].size();j++)
                if((k>>j)&1) v.push_back(b[i][j]);
            if(!mp[v]) mp[v]=++num;
            int x=mp[v],y=((int)v.size()%2==0?1:(-1));
            // modify(rt[x],1,n,i,y);
            p[i].push_back(mcp(x,y));
        }
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].x);
        Q[i].id=i;
    }
    sort(Q+1,Q+q+1,cmp);

    int o=0;
    vi u,z;
    for(int k=1;k<=q;k++){
        int l=Q[k].l,r=Q[k].r,x=Q[k].x,X;X=x;
        while(o<r){
            ++o;
            for(int i=0;i<p[o].size();i++) modify(rt[p[o][i].fi],1,n,o,p[o][i].se);
        }
        v.clear();
        for(int j=2;j*j<=x;j++)
            if(x%j==0){
                while(x%j==0) x/=j;
                v.push_back(j);
            }
        if(x!=1) v.push_back(x);
        int ans=0;z.clear();
        for(int i=0;i<(1<<(int)v.size());i++){
            u.clear();
            for(int j=0;j<v.size();j++)
                if((i>>j)&1) u.push_back(v[j]);
            if(mp[u]){
                ans+=query(rt[mp[u]],1,n,l,r);
                z.push_back(rt[mp[u]]);
            }
        }
        if(ans==0) Q[k].ans=-1;
        else if(gcd(A[r],X)==1) Q[k].ans=r;
        else{
            // int R=r;r-=1,ans=r;
            // while(l<=r){
            //     int mid=(l+r)>>1;
            //     int sum=0;
            //     for(int i=0;i<(1<<(int)v.size());i++){
            //         u.clear();
            //         for(int j=0;j<v.size();j++)
            //             if((i>>j)&1) u.push_back(v[j]);
            //         if(mp[u]){
            //             sum+=query(rt[mp[u]],1,n,mid,R);
            //         }
            //     }
            //     if(sum) l=mid+1,ans=mid;
            //     else r=mid-1;
            // }
            Q[k].ans=que(z,1,n);
        }
    }
    sort(Q+1,Q+q+1,cmpp);
    for(int i=1;i<=q;i++) printf("%d\n",Q[i].ans);
    return 0;
}
//减少定义，卡时 
/*
5 4
1 2 3 4 6
1 5 2
1 1 1
4 5 2
3 5 3 
*/