#include <bits/stdc++.h>


//speed coding

#define mp make_pair
#define cve(a) for (auto i : a) {cout << i << " ";  } cout << "\n";
#define f first
#define s second
#define loop(x, n) for (ll i = x; i < n; i++)
#define err cout << "ERROR" << endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) x.size()

// types
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
typedef long long ll;

// types of data
#define inf 1000000000
#define infll 1000000000000000000
#define mod 1000000009

using namespace std;

#define DEBUG 1

ll nod(ll a, ll b){
    if(a == -1){
        return b;
    }else if (b == -1){
        return a;
    }
    return __gcd(a, b);
}
struct sgt{
    vector<ll> t;
    ll d;
    sgt(vector<ll> &a){
        ll n = sz(a);
        ll k = 1;
        while(k < n){
            k*=2;
        }
        d = k;
        t.resize(2*d, -1);

        loop(d, d+n){
            t[i] = a[i-d];
        }
        for(ll i = d-1; i > 0; i--){
            t[i] = nod(t[2*i], t[2*i + 1]);
        }

    }
    ll gcd(ll l, ll r, ll lx, ll rx, ll v){
        if(lx > r || rx < l){
            return -1;
        }
        if(lx >= l && rx <= r){
            cout << "\nlx rx " << lx << " " << rx << " " << v  << " " << t[v] << endl;
            return t[v];
        }
        ll m = (lx + rx)/2;
        return nod(gcd(l, r, lx, m, 2*v ), gcd(l, r, m+1, r, 2 * v + 1));
    }
    ll gcd(ll l, ll r){
        return  gcd(l, r, 0, d-1, 1);
    }



};

void solve(){
    ll n, m;
    cin >> n;
    vector<ll> a(n);
    loop(0, n) cin >> a[i];
    sgt sg(a);
    cin >> m;
    loop(0, m){
        char t;
//        cin >> t;
        if(false){
//            ll j, x;
//            cin >> j >> x;;
//            j--;
//            sg.add(x, j);
        }else{
            ll l, r;
            cin >> l >> r;
            l--, r--;
            cout << sg.gcd(l,r) << " ";

        }
    }
    cout << "\n";
    for(auto i : sg.t){
        cout << i << " ";
    }
}

int main() {
#ifdef DEBUG
    freopen("text.txt", "r", stdin);
#else
    //    freopen("divisors.in", "r", stdin);
    //    freopen("divisors.out", "w", stdout);


#endif
//    int n;
//    cin >> n;
//    loop(0, n) {
//        solve();
//
//    }
    solve();
    return 0;
}