F спбгу need upd

/*
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃＼○／
┛┗┛┗┛┃ / /
┓┏┓┏┓┃ノ
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃┓
┛┗┛┗┛┃┃
      MIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSIC
*/

// #define pragma

#ifdef pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Wunused-result"
#endif // pragma

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define all(x) begin(x), end(x)
#define pb push_back
#define x first
#define y second
#define int long long
#define zero(two) memset(two, 0, sizeof(two))

using namespace std;
using namespace __gnu_pbds;


typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef long double ld;
typedef vector<vi> matrix;
template<typename T>
using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = atan2(0, -1);

void seriy() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);
    #if 1
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #endif
}

const int MAXN = 1e6 + 1;
const int INF = 1e9 + 7;

vi pr(MAXN, 1);
vi p;
vector<deque<int>> vm;
matrix prec(21);

int mul(deque<int> &st) {
    int ans = 1;
    for(auto i : st) {
        ans *= i;
    }
    return ans;
}

int cnt(int x, int i) {
    deque<int> cp = vm[i];
    int ans = 0;
    int ml = mul(cp);
    while(ans < x) {
        ans++;
        // cerr << cp.front() << '\n';
        ml = ml / cp.front() * (cp.front() - 1);
        int nw = cp.front();
        cp.pop_front();
        cp.push_front(nw - 1);
        if(nw - 1 == 1) {
            cp.pop_front();
        }
    }
    return ml;
}

signed main() {
    seriy();
    for(int i = 2; i < MAXN; i++) {
        if(pr[i]) {
            p.pb(i);
            if(i * 1ll * i < MAXN) {
                for(int j = i * i; j < MAXN; j += i) {
                    pr[j] = 0;
                }
            }
        }
    }
    pr[0] = 0;
    pr[1] = 0;
    int n;
    cin >> n;
    int a;
    vm.resize(n);
    vi ap;
    map<int, char> c;
    for(int i = 0; i < n; i++) {
        cin >> a;
        int k = a;
        c.clear();
        if(pr[k]) {
            vm[i].push_back(2);
            continue;
        }
        for(int j = 0; j < (int)p.size(); j++) {
            if(p[j] > k) {
                break;
            }
            while(k % p[j] == 0) {
                if(c[p[j]] == 0) {
                    c[p[j]] = 2;
                }
                else {
                    c[p[j]]++;
                }
                k /= p[j];
            }
        }
        for(auto &[k, v] : c) {
            ap.pb(v);
        }
        sort(all(ap));
        for(auto j : ap) {
            if(j > 1) vm[i].push_back(j);
        }
        ap.clear();
    }

    for(int i = 0; i < 21; i++) {
        t[i].resize(4 * MAXN);
        prec[i].resize(n);
        for(int j = 0; j < n; j++) {
            prec[i][j] = cnt(i, j);
        }
        build(i, 0, 0, n - 1);
    }

    int q;
    cin >> q;
    vi l(q), r(q), x(q);
    for(int i = 0; i < q; i++) {
        cin >> l[i] >> r[i] >> x[i];
        l[i]--;
        r[i]--;
        x[i] = min(240, x[i]);
        int mn = 0;
        for(int j = 0; j < 21; j++) {
            int cur = get(j, 0, 0, n - 1, l[i], r[i]);
            if(cur <= x) {
                mn = cur;
                break;
            }
        }

    }
    return 0;
}