#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;
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) {
		return g;
	}
	int ans=gcd(g,getgcd(l,r-1));
	ans=max(ans,gcd(g,getgcd(l+1,r)));
	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))));
	}
	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(i==40) {
			cout<<l<< " "<<r<<" "<<k<<endl;
			for(int j=l;j<=r;j++) {
				cout<<a[j]<<" ";
			}
			puts("");
		}
		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
*/