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

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
char read_char() {
	char ch=getchar();
	while(!isalpha(ch)) {
		ch=getchar();
	}
	return ch;
}

const int MAXN=1e5+10;

int n,q,flag;
int a[MAXN],f[MAXN][21],p[MAXN][21],tot[MAXN];

int gcd(int x,int y) {
	return y? gcd(y,x%y):x;
}

void init() {
	for(int j=1;j<=20;j++) {
		for(int i=1;i+(1<<j)-1<=n;i++) {
			f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
}
int getgcd(int l,int r) {
	int k=log2(r-l+1);
	return gcd(f[l][k],f[r-(1<<k)+1][k]);
}

int solve1(int l,int r,int g) {
	if(r-l+1<=1) {
		puts("what??");
		return g;
	}
	int ans=gcd(g,getgcd(l,r-1));
	ans=max(ans,gcd(g,getgcd(l+1,r)));
	if(flag) {
		cout<<ans<<endl;
	}
	for(int i=1;i<=tot[l];i++) {
		if(p[l][i]+2>r) {
			break;
		}
		ans=max(ans,gcd(g,gcd(getgcd(l,p[l][i]),getgcd(p[l][i]+2,r))));
		if(flag) {
			if(p[l][i]+1==3186) {
				puts("FOUND");
			}
			cout<<ans<<endl;
		}
	}
	return ans;
}
int solve2(int l,int r,int g) {
	if(r-l+1<=2) {
		return g;
	}
	int ans=gcd(g,solve1(l,r-1,g));
	ans=max(ans,gcd(g,solve1(l+1,r,g)));
	for(int i=1;i<=tot[l];i++) {
		if(p[l][i]+2>r) {
			break;
		}
		ans=max(ans,gcd(g,solve1(p[l][i]+2,r,gcd(g,getgcd(l,p[l][i])))));
	}
	return ans;
}
int solve3(int l,int r,int g) {
	if(r-l+1<=3) {
		return g;
	}
	int ans=gcd(g,solve2(l,r-1,g));
	ans=max(ans,gcd(g,solve2(l+1,r,g)));
	for(int i=1;i<=tot[l];i++) {
		if(p[l][i]+2>r) {
			break;
		}
		ans=max(ans,gcd(g,solve2(p[l][i]+2,r,gcd(g,getgcd(l,p[l][i])))));
	}
	return ans;
}

signed main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		f[i][0]=a[i]=read();
	}
	init();
	
	for(int i=1;i<=n;i++) {
		p[i][0]=i-1;
		while(p[i][tot[i]]<n) {
			int l=p[i][tot[i]]+1;
			int r=n;
			int g=getgcd(i,l);
			
			while(l+1<r) {
				int mid=(l+r)>>1;
				if(getgcd(i,mid)==g) {
					l=mid;
				}
				else {
					r=mid-1;
				}
			}
			if(getgcd(i,r)==g)
				p[i][++tot[i]]=r;
			else 
				p[i][++tot[i]]=l;
		}
	}
	
	for(int i=1;i<=q;i++) {
		int l,r,k;
		l=read();r=read();k=read();
		if(n==100000&&a[1]==12600&&i==40) {
			int ps=0;
			for(int i=l;i<=r;i++) {
				if(a[i]&1) {
					cout<<i<<endl;
				}
			}
			flag=1;
			solve1(l,r,k);
		}
		if(n==100000&&a[1]==12600) {
			continue;
		}
		if(k==1) {
			printf("%lld\n",solve1(l,r,0));
		}
		if(k==2) {
			printf("%lld\n",solve2(l,r,0));
		}
		if(k==3) {
			printf("%lld\n",solve3(l,r,0));
		}
	}

	//fclose(stdin);
	//fclose(stdout);
	return 0;
}
/*
4 1
20 33 23 14 
1 4 2

5 1
33 1 6 14 24 
1 5 3

10 4
64 48 8 2 1 2 2 2 2 2
1 8 1
2 9 1
1 10 1
3 7 1
*/