#include <bits/stdc++.h>
using namespace std;
const int MM = 1e5+5,LG = 20;
int n,q; int64_t t[MM][LG]; // store gcd of interval [i,i+2^j)
int64_t query(int a, int b){
    if(a > b) return 0;
    b++;
    int dep = 31-__builtin_clz(b-a);
    return gcd(t[a][dep],t[b-(1<<dep)][dep]);
}
int64_t go(int l, int r, int k){
    if(l > r) return k ? 1 : 0;
    if(k == 0) return query(l,r);
    if(k == r-l+1) return 0;
    // find change points
    int p = l;
    vector<int> ch = {l};
    while(1){
        // find first value where gcd changes  
        int u = p; int64_t st = t[p][0];
        for(int j = LG-1; j >= 0; j--) if(u+(1<<j)-1 <= r){
            if(t[u][j] == st){
                u += (1<<j)-1;
            }
        }
        u++;
        if(u > r) break;
        ch.push_back(u); 
        p = u;
    }
    int64_t bst = 0;
    for(int x : ch){
        bst = max(bst,gcd(query(l,x-1),go(x+1,r,k-1)));
    }
    return bst;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> t[i][0];
    for(int j = 1; j < LG; j++) for(int i = 1; i+(1<<j)-1 <= n; i++) t[i][j] = gcd(t[i][j-1],t[i+(1<<(j-1))][j-1]);
    while(q--){
        int l,r,k; cin >> l >> r >> k;
        cout << go(l,r,k) << "\n";
    }
}
// for k = 1, check all change points
// for k = 2, check first, and then find remaining change points: 60^2 log N
// for k = 3, check first, find remaining, find remaining 60^3 log N

answer.code: In function ‘int64_t query(int, int)’:
answer.code:9:12: error: ‘gcd’ was not declared in this scope
    9 |     return gcd(t[a][dep],t[b-(1<<dep)][dep]);
      |            ^~~
answer.code: In function ‘int64_t go(int, int, int)’:
answer.code:33:23: error: ‘gcd’ was not declared in this scope
   33 |         bst = max(bst,gcd(query(l,x-1),go(x+1,r,k-1)));
      |                       ^~~
answer.code: In function ‘int main()’:
answer.code:41:80: error: ‘gcd’ was not declared in this scope
   41 |     for(int j = 1; j < LG; j++) for(int i = 1; i+(1<<j)-1 <= n; i++) t[i][j] = gcd(t[i][j-1],t[i+(1<<(j-1))][j-1]);
      |                                                                                ^~~