//
// Created by Barichek on 20.07.2023 09:49:54
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e5+10, inf = 1000111222;

const int max_lev=__lg(max_n)+1;

struct sparse_table {
    ll mn[max_lev][max_n];

    void init(int n, ll a[]) {
        for (int i = 0; i < n; ++i) {
            mn[0][i] = a[i];
        }
        for (int i = 1; i < max_lev; ++i) {
            for (int j = 0; j + (1 << i) <= n; ++j) {
                mn[i][j] = __gcd(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    ll get_min(int l, int r) const {
        if (l > r) {
            return 0;
        }
        const int lev = 31 - __builtin_clz(r - l + 1);
        return __gcd(mn[lev][l], mn[lev][r - (1 << lev) + 1]);
    }
};

sparse_table st;

ll a[max_n];
vector<int> nxt[max_n];

ll get_ans(int l,int r,int k,ll input)
{
    if (l>r){
        return input;
    }
    ll res=__gcd(input,st.get_min(l,r));
    if (k!=0){
        res=max(res,get_ans(l+1,r,k-1,input));
        for (auto i:nxt[l]){
            if (i<r){
                ll there=get_ans(i+2,r,k-1,__gcd(input,st.get_min(l,i)));
                res=max(res,there);
            }
        }
    }
    LOG(l,r,k,input,res);
    return res;
}

int main() {
//    freopen("input_l.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,q;
    cin>>n>>q;
    for (int i=0;i<n;i++){
        cin>>a[i];
    }
    st.init(n,a);
    for (int i=0;i<n;i++){
        int pos=i-1;
        while (pos!=n-1){
            int l=pos+1,r=n-1;
            while (r-l>0){
                int m=(l+r)/2+1;
                if (st.get_min(i,pos+1)==st.get_min(i,m)){
                    l=m;
                }
                else{
                    r=m-1;
                }
            }
            nxt[i].pb(l);
            pos=l;
        }
    }
    while (q--){
        int l,r,k;
        cin>>l>>r>>k;
        l--;
        r--;
        cout<<get_ans(l,r,k,0)<<"\n";
    }
    return 0;
}