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

constexpr int maxn=100000;
constexpr int sz=316;
int pcnt=0;
int prim[maxn+50];
int notp[maxn+50];
int minp[maxn+50];
void prepare(){
	notp[1]=0;
	for (int i=2;i<=maxn;i++){
		if (!notp[i]){
			prim[++pcnt]=i;
			minp[i]=i;
		}
		for (int j=1,x=1;j<=pcnt && (x=i*prim[j])<=maxn;j++){
			notp[x]=1;
			if (i%prim[j]==0){
				minp[x]=prim[j];
				break;	
			}
			else{
				minp[x]=prim[j];
			}
		}
	}
}

int n,Q;
int a[maxn+50];
vector<int> g[maxn+50];
vector<int> v[maxn+50];
bitset<maxn+2> s[sz+5];

vector<tuple<int,int,int>> q[maxn+50];
int ans[maxn+50];

void dfs(int x,bitset<maxn+2> &now){
	/*
	if (x<=10){
		cerr << "x: " << x << endl;
		for (int i=0;i<=10;i++) cerr << now[i];
		cerr << endl; 	
	}
	*/
	{
		for (auto [l,r,id]:q[x]){
			int pos=now._Find_next(n-r);
			pos=n-pos+1;
			if (pos<l) ans[id]=-1;
			else ans[id]=pos; 
		}
	}
	for (auto y:g[x]){
		int p=y/x;
		bitset<maxn+2> nxt=now;
		if (p<=sz) nxt=nxt&s[p];
		else{
			for (auto e:v[p]) nxt[e]=0;	
		}
		dfs(y,nxt);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	prepare();
	/*
	for (int i=1;i<=10;i++) cout << prim[i] << " ";
	cout << endl;
	for (int i=1;i<=10;i++) cout << minp[i] << " ";
	cout << endl;
	*/
	cin >> n >> Q;
	for (int i=1;i<=n;i++) cin >> a[i];
	
	for (int i=1;i<=Q;i++){
		int l,r,x;
		cin >> l >> r >> x;
		q[x].emplace_back(l,r,i);
	}
	
	for (int i=2;i<=maxn;i++) g[i/minp[i]].push_back(i);
//	cerr << "ok" << endl;
	for (int i=1;i<=n;i++){
		for (int now=a[i];now!=1;){
			int p=minp[now];
			
			if (p<=sz) s[p][n-i+1]=1;
			else v[p].push_back(n-i+1);
			
			now/=p;
		}
	}
	{
		for (int i=1;i<=sz;i++) s[i]=~s[i];
	}
	/*
	for (int i=1;i<=10;i++){
		for (int j=0;j<=10;j++){
			cerr << s[i][j];
		}
		cerr<< endl;
	}
	*/
	bitset<maxn+2> now;
	now=~now;
	dfs(1,now);
	for (int i=1;i<=Q;i++) cout << ans[i] << "\n";
	return 0;	
}