#include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=,M=,S=,mod=1e6+;

 bool b[S];

 int n,Q,mx,nd,l,r,tot,ans,idx[S],lst[S],rt[N],a[N],sm[N],p[S],v[M],ls[M],rs[M];

 int ksm(int a,int b){

     int res=;

     for (; b; a=1ll*a*a%mod,b>>=)

         if (b & ) res=1ll*res*a%mod;

     return res;

 }

 int inv(int x){ return ksm(x,mod-); }

 void init(int n){

     rep(i,,n){

         if (!b[i]) p[++tot]=i,idx[i]=tot;

         for (int j=; j<=tot && p[j]*i<=n; j++){

             b[p[j]*i]=;

             if (i%p[j]==) break;

         }

     }

 }

 void ins(int &x,int y,int L,int R,int pos,int k){

     x=++nd; v[x]=v[y]; ls[x]=ls[y]; rs[x]=rs[y];

     if (L==R){ v[x]=1ll*v[x]*(k-)%mod*inv(k)%mod; return; }

     int mid=(L+R)>>;

     if (pos<=mid) ins(ls[x],ls[y],L,mid,pos,k);

         else ins(rs[x],rs[y],mid+,R,pos,k);

     v[x]=1ll*v[ls[x]]*v[rs[x]]%mod;

 }

 int que(int x,int y,int L,int R,int pos){

     if (!x && !y) return ;

     if (L==R) return 1ll*v[y]*inv(v[x])%mod;

     int mid=(L+R)>>;

     if (pos<=mid) return que(ls[x],ls[y],L,mid,pos);

         else return 1ll*v[ls[y]]*inv(v[ls[x]])%mod*que(rs[x],rs[y],mid+,R,pos)%mod;

 }

 int main(){

     scanf("%d%d",&n,&Q); sm[]=; v[]=;

     rep(i,,n) scanf("%d",&a[i]),sm[i]=1ll*sm[i-]*a[i]%mod,mx=max(mx,a[i]);

     init(mx);

     rep(i,,n){

         rt[i]=rt[i-]; int t=a[i];

         for (int j=; j<=tot && p[j]*p[j]<=t; j++)

             if (t%p[j]==){

                 ins(rt[i],rt[i],,n,lst[j],p[j]); lst[j]=i;

                 while (t%p[j]==) t/=p[j];

             }

         if (t>) ins(rt[i],rt[i],,n,lst[idx[t]],t),lst[idx[t]]=i;

     }

     rep(i,,Q){

         scanf("%d%d",&l,&r); l^=ans; r^=ans;

         printf("%d\n",ans=(1ll*sm[r]*inv(sm[l-])%mod*que(rt[l-],rt[r],,n,l-)%mod));

     }

     return ;

 }