#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native,popcnt,lzcnt,abm,bmi,bmi2,fma")
using namespace __gnu_pbds;
using namespace std;
using LL = long long;


struct MyHash {
    LL operator()(pair<int, int> x) const {
        return ((1LL * x.first) << 31)  + x.second;
    }
};

const int N = 1e6 + 5;
int n, q;
int a[N];
vector<int> P[N];
struct qr {
    int x, y, v, type;
} node[N * 36], tmp[N * 36];
int ans[N];
void cdq(int l, int r) {
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int p = l, q = mid + 1;
    int mx = 0, t = 0;
    while (p <= mid && q <= r) {
        if (node[p].x >= node[q].x) {
            if (node[p].type == 0)
                mx = max(mx, node[p].v);
            tmp[++t] = node[p];
            p++;
        } else if (node[p].x < node[q].x) {
            if (node[q].type == 1)
                ans[node[q].v] = max(ans[node[q].v], mx);
            tmp[++t] = node[q];
            q++;
        }
    }
    while (p <= mid) {
        if (node[p].type == 0)
            mx = max(mx, node[p].v);
        tmp[++t] = node[p];
        p++;
    }
    while (q <= r) {
        if (node[q].type == 1)
            ans[node[q].v] = max(ans[node[q].v], mx);
        tmp[++t] = node[q];
        q++;
    }
    for (int i = l; i <= r; i++)
        node[i] = tmp[i - l + 1];
}
int m;
int query(const vector<int> &v, int p) {
    int l = 0, r = (int)(v.size()) - 1, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (v[mid] >= p)
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int lim = sqrt(a[i]);
        for (int j = 1; j <= lim; j++) {
            if (a[i] % j == 0) {
                P[j].push_back(i);
                if (j * j != a[i])
                    P[a[i] / j].push_back(i);
            }
        }
    }
    gp_hash_table<pair<int, int>, int, MyHash> table;

    for (int i = 1; i <= 1000000; i++) {
        int lim = P[i].size();
        for (int j = 0; j < lim - 1; j++) {
            int t = P[i][j + 1] * 2 - P[i][j];
            int r = query(P[i], t);
            if (r != -1) {
                table[{P[i][j], P[i][r]}] = max(table[{P[i][j], P[i][r]}], i);
                // cout<<P[i][j]<<' '<<P[i][j+1]<<' '<<i<<' '<<P[i][r]<<'\n';
                // node[++m] = {P[i][j], P[i][r], i, 0};
            }
        }
    }
    for (const auto [x, y] : table) {
        node[++m] = {x.first, x.second, y, 0};
    }
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        node[++m] = {l, r, i, 1};
    }
    sort(node + 1, node + m + 1, [](const qr &a, const qr &b) { return a.y == b.y ? (a.x == b.x ? a.type < b.type : a.x > b.x) : a.y < b.y; });
    cdq(1, m);
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}