#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 200010;

ll a[N], f[N][20], b[N];
int mi[N];
vector<int> ksj[N];

ll query(int l, int r) {
    if (l > r) return 0;
    int k = mi[r - l + 1];
    return __gcd(f[l][k], f[r - (1 << k) + 1][k]);
}

vector<int> calc(int l, ll x) {
    vector<int> ans;
    int sz = ksj[l].size();
    for (int i = 0; i < sz; i++) {
        b[i] = __gcd(x, query(l, ksj[l][i]));
    }
    rep (i, 0, sz-1) {
        if (i == 0 || b[i] != b[i-1]) ans.pb(ksj[l][i]);
    }
    return ans;
}

vector<int> s1, s2, s3;

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    rep (i, 2, n) mi[i] = mi[i>>1]+1;
    rep (i, 1, n) {
        scanf("%lld", &a[i]);
        f[i][0] = a[i];
    }//cout <<"#";
    rep (j, 1, 16) {
        rep (i, 1, n) {
            f[i][j] = __gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    ksj[n].push_back(n);
    for (int i = n-1; i >= 1; i--) {
        ksj[i] = calc(i+1, a[i]);
        if (query(i, ksj[i][0]) != a[i]) ksj[i].insert(ksj[i].begin(), i);
        else ksj[i][0] = i;
    }

    while (q--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        ll ans = 1;
        if (k == 1) {
            s1 = calc(l, 0);
            for (auto i: s1) {
                if (i > r) break;
                ans = max(ans, __gcd(query(l, i-1), query(i+1, r)));
            }
        } else if (k == 2) {
            s1 = calc(l, 0);
            for (auto i: s1) {
                if (i > r) break;
                ll g1 = query(l, i-1);
                s2 = calc(i+1, g1);
                for (auto j: s2) {
                    if (j > r) break;
                    ll g2 = query(i+1, j-1);
                    ans = max(ans, __gcd(g1, __gcd(g2, query(j+1, r))));
                }
            }
        } else {
            s1 = calc(l, 0);
            for (auto i: s1) {
                if (i > r) break;
                ll g1 = query(l, i-1);
                s2 = calc(i+1, g1);
                for (auto j: s2) {
                    if (j > r) break;
                    ll g2 = query(i+1, j-1);
                    s3 = calc(j+1, __gcd(g1, g2));
                    for (auto w: s3) {
                        ll g3 = query(j+1, w-1);
                        ans = max(ans, __gcd(__gcd(g1, g2), __gcd(g3, query(w+1, r))));
                    }
                }
            }
        }
        cout << ans<<'\n';
    }

    return 0;
}

/*
4 1
3 2 6 4
1 3 1


9 11
24 36 6 72 12 18 24 36 6
1 9 1
1 9 2
1 9 3
1 5 1
1 5 2
1 5 3
4 8 1
4 8 2
4 8 3
4 9 3
4 7 2

*/