#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int N=1e5+1,M=9592;
int pr[N],mn[N],id[N],cnt;
bitset<N> s[M],t;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	{
		int n=1e5,i,j;
		for (i=2; i<=n; i++)
		{
			if (!mn[i]) mn[i]=i,id[i]=cnt,pr[cnt++]=i;
			for (j=0; i*pr[j]<=n; j++)
			{
				mn[i*pr[j]]=pr[j];
				if (i%pr[j]==0) break;
			}
		}
	}
	int n,m,i;
	cin>>n>>m;
	vector<vector<int>> w(n);
	for (i=0; i<M; i++) s[i].set();
	for (i=0; i<n; i++)
	{
		int x,y;
		cin>>x;
		while (x>1)
		{
			y=mn[x]; x/=y;
			while (x%y==0) x/=y;
			w[i].push_back(y=id[y]);
			s[y].reset(n-i-1);
		}
	}
	while (m--)
	{
		int l,r,x;
		cin>>l>>r>>x;
		--l; --r;
		l=n-l-1; r=n-r-1;
		swap(l,r);
		t.set();
		vector<int> w;
		{
			int y;
			while (x>1)
			{
				y=mn[x]; x/=y;
				while (x%y==0) x/=y;
				w.push_back(y=id[y]);
			}
		}
		for (int p:w) t&=s[p];
		int ans=t._Find_next(l-1);
		if (ans<=r) cout<<n-ans<<'\n';
		else cout<<"-1\n";
	}
}