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

const int M=1e5+10;
vector<int>G[M];
int pri[M],id[M],ans[M],A[M];
bitset<M>B[355];
struct QQQ{
	int l,r,id;
};
vector<QQQ>Q[M];
void init(){
	for(int i=2;i<M;++i){
		if((int)G[i].size()==0){
			pri[++pri[0]]=i,id[i]=pri[0];
			for(int j=i;j<M;j+=i)
				G[j].push_back(i);
		}
	}
}
int main(){
	init();
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
		scanf("%d",&A[i]);
	int S=350;
	for(int i=1;pri[i]<=S;++i)
		for(int j=1;j<=n;++j)
			if(A[j]%pri[i]==0)
				B[i][n-j+1]=1;
	for(int i=1;i<=q;++i){
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		if(x==1)ans[i]=r;
		else Q[x].push_back((QQQ){l,r,i});	
	}
	for(int i=2;i<M;++i){
		if(Q[i].empty())continue;
		bitset<M>res;
		int D=0;
		for(int j=0;j<(int)G[i].size();++j)
			if(G[i][j]<=S)res|=B[id[G[i][j]]];	
			else D=G[i][j];
		res=~res;
		for(int j=0;j<(int)Q[i].size();++j){
			auto [l,r,id]=Q[i][j];
			int nw=res._Find_next(n-r);
			if(D==0){
				nw=n-nw+1;
				ans[id]=nw>=l?nw:-1;
			}else{
				while(nw<=n-l+1&&A[n-nw+1]%D==0)
					nw=res._Find_next(nw);
				nw=n-nw+1;
				ans[id]=nw>=l?nw:-1;
			}
		}
	}
	for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
	return 0;
}