#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,q;
int a[N];
vector<int>P[N];
struct qr
{
    int x,y,v,type;
}node[N*200],tmp[N*200];
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=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);
            }
        }
    }
    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)
            {
                //cout<<P[i][j]<<' '<<P[i][j+1]<<' '<<i<<' '<<P[i][r]<<'\n';
                node[++m]={P[i][j],P[i][r],i,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';
}

/tmp/ccMvW1pv.o: in function `__tcf_0':
answer.code:(.text+0x8): relocation truncated to fit: R_X86_64_PC32 against symbol `P' defined in .bss section in /tmp/ccMvW1pv.o
/tmp/ccMvW1pv.o: in function `void std::__insertion_sort<qr*, __gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(qr const&, qr const&)#1}> >(qr*, __gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(qr const&, qr const&)#1}>, __gnu_cxx::__ops::_Iter_comp_iter<main::{lambda(qr const&, qr const&)#1}>) [clone .constprop.0]':
answer.code:(.text+0x57): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0xdb): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0xf0): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0xff): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0x110): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0x199): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
/tmp/ccMvW1pv.o: in function `cdq(int, int) [clone .part.0]':
answer.code:(.text+0x20f): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0x2de): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0x36c): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in /tmp/ccMvW1pv.o
answer.code:(.text+0x3d4): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status