#include <bits/stdc++.h>

using namespace std;

#if __cplusplus >= 201103L
    struct pairhash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        template<class T, class U>
        size_t operator() (const pair<T,U> &p) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(p.first + FIXED_RANDOM) ^ splitmix64(p.second+ FIXED_RANDOM);
        }
    };
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
    inline int randint(int l, int r) {
        return uniform_int_distribution<int>(l,r)(rng);
    }
    inline double randdouble(double l, double r) {
        return uniform_real_distribution<double>(l,r)(rng);
    }
#endif
 
#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) 0
#endif

#define fastio ios::sync_with_stdio(false); cin.tie(0);
#define ll long long
#define ull unsigned long long
#define ll128 __int128_t
#define PI 3.14159265358979323846
#define abs(a) ((a>0)?a:-(a))
#define pii pair<int,int>
#define pll pair<ll,ll>

const long double pi = acos(-1.0);
const long double eps = (double)1e-2;

int mod = (1<<30);

template<class T>
T qpow(T a, int b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm((int)(x % mod))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(mod - x));
    }
    Z inv() const {
        assert(x != 0);
        return qpow(*this, mod - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = (ll)(x) * rhs.x % mod;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

const int maxn = 1e5+5;
const int maxm = 4e4+55;


int n,q;
ll gcd(ll a, ll b) {
    if (!b) return a;
    return gcd(b, a%b);
}
ll a[maxn];

struct SparseTable {
    ll st[maxn][18], bin[maxn];
    ll ask_st(int l, int r) {
        int len = r-l+1;
        int k = bin[len];
        return gcd(st[l][k], st[r-(1<<k)+1][k]);
    }
 
    void build_st() {
        bin[1] = 0; bin[2] = 1;
        for (int i = 3; i < maxn; i++) bin[i] = bin[i>>1] + 1;
        for (int i = 1; i <= n; i++) st[i][0] = a[i];
        for (int k = 1; k < 18; k++) {
            for (int i = 1; i + (1<<k) - 1 <= n; i++)
                st[i][k] = gcd(st[i][k-1], st[i+(1<<(k-1))][k-1]);
        }
    }
} st;

vector<int> nxt[maxn];  // nxt[i]: 储存了从 i 开始，所有不同的 gcd 的右端点j的最大值

ll solve(int l, int r, int k, ll g) {
    assert(r-l+1 > k);
    assert(l <= r);
    if (k == 0) return st.ask_st(l,r);

    ll ans = 1;
    for (int j : nxt[l]) {
        while (r-j <= k) j--;
        // printf("l = %d, r = %d, j = %d, k = %d, st(l,j) = %lld, solve(j+2,r,k-1) = %lld\n",l,r,j,k,st.ask_st(l,j), solve(j+2,r,k-1));
        // LOG(j);
        // LOG(st.ask_st(l,j));
        // LOG(solve(j+2, r, k-1));
        ll G = gcd(g, st.ask_st(l, j));
        ans = max(ans, solve(j+2, r, k-1, G));
    }
    ans = max({ans, solve(l, r-1, k-1, g), solve(l+1, r, k-1, g)});
    return ans;
}

int main() {
    fastio;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    st.build_st();
    for (int i = 1; i <= n; i++) {
        int j = i;

        while (j <= n) {
            int low = j, high = n, res = j;
            ll g = st.ask_st(i, j);
            while (low <= high) {
                int mid = (low + high) >> 1;
                if (st.ask_st(i, mid) == g) res = mid, low = mid+1;
                else high = mid-1;
            }
            nxt[i].push_back(res);
            j = res + 1;
        }

        // for (int j : nxt[i]) {
        //     printf("i = %d, j = %d, gcd = %lld\n",i,j,st.ask_st(i,j));
        // }
    }


    while (q--) {
        int l,r,k; cin >> l >> r >> k;
        cout << solve(l,r,k,0) << "\n";
    }
    // LOG(solve(3,4,1));
    // solve(3,4,1);
}