#include <bits/stdc++.h>

#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size) memset(array, value, ((size) + 5) * sizeof(decltype(array[0])))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v) (sort(vecall(v), greater<decltype(v.back())>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
#define vecunique(v) ((v).resize(unique(vecall(v)) - (v).begin()))
using namespace std;
using db = long double;
const int N = 2e5 + 50;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const db PI = acos(-1.0L);

int n, q;

ll g[20][N], lg2[N];
ll a[N];
void init()
{
    for (int i = 1; i <= n; i++)
        g[0][i] = a[i];
    for (int b = 1; b < 20; b++)
        for (int i = 1; i + (1 << b) - 1 <= n; i++)
            g[b][i] = __gcd(g[b - 1][i], g[b - 1][i + (1 << (b - 1))]);
}

ll qg(int l, int r)
{
    if (l > r) return 0;
    int k = lg2[r - l + 1];
    return __gcd(g[k][l], g[k][r - (1 << k) + 1]);
}

vector<ll> vec[N];

ll work(int l, int r, int k, ll val)
{
    if (k == 0)
        return __gcd(val, qg(l, r));
    if (k >= r - l + 1)
        return 0;
    ll ret = 0;
    for (auto nxt : vec[l])
    {
        if (nxt > r)
            break;
        ll res = work(nxt + 1, r, k - 1, __gcd(val, qg(l, nxt - 1)));
        ret = max(ret, res);
    }
    return ret;
}

inline void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init();

    vec[n].push_back(n);
    for (int l = n - 1; l >= 1; l--)
    {
        ll las = a[l];
        for (auto r : vec[l + 1])
        {
            ll gc = qg(l, r);
            if (gc != las)
                las = gc, vec[l].push_back(r);
        }
        vec[l].push_back(l);
        sort(vec[l].begin(), vec[l].end());
        vec[l].erase(unique(vec[l].begin(), vec[l].end()), vec[l].end());
    }

    while (q--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        ll ans = work(l, r, k, 0);
        cout << ans << '\n';
    }
}

int main()
{
    for (int i = 2; i < N; i++)
        lg2[i] = lg2[i >> 1] + 1;
// #define MULTIPLE_CASE
#define CLOSE_IOS
#ifdef CLOSE_IOS
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
    int Test = 1;
#ifdef MULTIPLE_CASE
#ifdef CLOSE_IOS
    cin >> Test;
#else
    scanf("%d", &Test);
#endif
#endif
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    return 0;
}