#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
#include<array>
#include<cmath>
using namespace std;
using LL = long long;

// int tr[150005];

// int lowbit(int x){
//     return x & -x;
// }

// void modify(int x, int v){
//     while(x <= 150'000){
//         tr[x] = max(tr[x], v);
//         x += lowbit(x);
//     }
// }

// int query_max(int x){
//     int ans = 0;
//     while(x){
//         ans = max(ans, tr[x]);
//         x -= lowbit(x);
//     }
//     return ans;
// }

int mx[150005], mx1[150005];


int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int N = 1e6;
    int n, m;
    cin >> n >> m;
    vector<vector<int> > pos(N + 1);
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        for(int j = 1; j * j <= t; j++){
            if (t % j == 0){
                pos[j].push_back(i);
                if (j * j != t){
                    pos[t / j].push_back(i);
                }
            }
        }
    }
    vector<vector<pair<int, int> > > seg(n + 1);
    for(int i = 1; i <= N; i++){
        if (!pos[i].empty()){
            for(int j = 0; j + 1 < pos[i].size(); j++){
                int a = pos[i][j], b = pos[i][j + 1];
                int k = lower_bound(pos[i].begin(), pos[i].end(), 2 * b - a) - pos[i].begin();
                if (k != pos[i].size()) seg[a].push_back({pos[i][k], i});
            }
        }
    }
    vector<vector<pair<int, int> > > query(n + 1);
    vector<int> ans(m);
    for(int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        query[l].push_back({r, i});
    }
    const int len = sqrt(n) + 1;
    for(int i = n; i >= 1; i--){
        for(auto [r, val] : seg[i]){
            mx[r] = max(mx[r], val);
            mx1[(r + len - 1) / len] = max(mx1[(r + len - 1) / len], val);
        }
        for(auto [r, id] : query[i]){
            for(int j = 1; ; j++){
                if (j * len <= r) ans[id] = max(ans[id], mx1[j]);
                else{
                    for(int k = (j - 1) * len + 1; k <= r; k++) ans[id] = max(ans[id], mx[k]);
                    break;
                }
            }
        }
    }
    for(auto x : ans) cout << x << '\n';

}