#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
// #define int long long
 
#define dbg_loc() cerr << __PRETTY_FUNCTION__ << " : " << __LINE__ << "\n"
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p){ 
	return os << '(' << p.first << ", " << p.second << ')'; 
}
template<typename T_container,typename T=typename enable_if<!is_same<T_container,string>::value, typename T_container::value_type>::type> 
ostream& operator<<(ostream &os, const T_container &v){ 
	os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; 
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
	cerr << ' ' << H; 
	dbg_out(T...); 
}
#define LOCAL
#define LOCAL
#ifdef LOCAL 
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
 
///CUIDADO COM MAXN
#define N 100020 // 1E6
 
ll dp[N*10][30];
int n, q;
vector<ll> v;
inline void build(){
  for(int i = 0; i < n; i++) dp[i][0] = v[i];
  for(int j = 1; j <= 19; j++)
      for(int i = 0; i < n; i++)
           dp[i][j] = gcd(dp[i][j - 1], dp[ i + (1<<(j - 1)) ][j - 1]);
}

inline ll query(int l, int r){
	if(l == r) return v[l];
	int exp = 31-__builtin_clz(r-l);
	return gcd(dp[l][exp], dp[r - (1<<exp) + 1][exp]);
}

map<pair<int, ll>, int> mapa;
int prox(int i, ll x){
	if(mapa.find({i, x}) != mapa.end()) return mapa[{i, x}];
	int ini = i+1, fim = sz(v) - 1, mid, best = sz(v);
	while(fim>=ini){
		mid=(ini+fim)/2;
		ll d = query(i,mid);
		if(d != x) best=mid,fim=mid-1;
		else ini=mid+1;
	}
	return mapa[{i,x}] = best;
}
 
map< pair<int, ll>, ll> vis;

ll solve(int i, ll x, int l, int r, int k){
	if(i > r){
		if(k == 0) return x;
		return -1;
	}
	if(vis.find({i,x})  != vis.end()) return vis[{i, x}];

	if(k == 0){
		return gcd(x,query(i, r));
	}
	// se eu for manter o x, tento remover o proximo
	ll d = gcd(v[i],x);
	ll A = solve(prox(i, x), d,l,r,k);

	//remove o i
	ll B = solve(i + 1, x, l, r, k-1);

	return  vis[{i,x}] = max(A, B);
}

void solve_case(){
	cin>>n>>q;
	v.resize(n);
	for(int i=0;i < n;i++) cin>>v[i];
	build();

	while(q--){
		int l, r, k;
		cin>>l>>r>>k;
		--l, --r;
		vis.clear();
		cout<<solve(l,0,l,r,k)<<"\n";
	}
 
}
 
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int test_case=1;
	// cin>>test_case;
	while(test_case--){
		solve_case();
	}
}