#include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n,m,sum,sz,num[],l[],r[],plv[][],mode[][],mplv[][];

 int a[],en,Time[],x,y,ma[],ans;

 struct Point{int v,p;}b[];

 bool operator < (const Point &a,const Point &b){return a.v<b.v;}

 int Res,Num;char C,CH[];

 inline int G()

 {

     Res=;C='*';

     while(C<''||C>'')C=getchar();

     while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}

     return Res;

 }

 inline void P(int x)

 {

     Num=;if(!x){putchar('');puts("");return;}

     while(x>)CH[++Num]=x%,x/=;

     while(Num)putchar(CH[Num--]+);

     puts("");

 }

 void makeblock()

 {

     sz=(int)sqrt((double)n); if(!sz) sz=;

     for(sum=;sum*sz<n;sum++)

       {

         l[sum]=r[sum-]+;

         r[sum]=sum*sz;

         for(int i=l[sum];i<=r[sum];i++) num[i]=sum;

       }

     l[sum]=r[sum-]+;

     r[sum]=n;

     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;

 }

 void LiSan()

 {

     sort(b+,b+n+);

     for(int i=;i<=n;i++)

       {

         if(b[i].v!=b[i-].v) en++;

         ma[a[b[i].p]=en]=b[i].v;

       }

 }

 void makeplv()

 {

     for(int i=;i<=n;i++)

       for(int j=num[i];j<=sum;j++)

         plv[a[i]][j]++;

 }

 void makemode()

 {

     for(int i=;i<=sum;i++)

       {

         memset(Time,,sizeof(Time));

         int modenow,modeplv=;

         for(int j=i;j<=sum;j++)

           {

             for(int k=l[j];k<=r[j];k++)

               {

                 Time[a[k]]++;

                 if(Time[a[k]]>modeplv||(Time[a[k]]==modeplv&&a[k]<modenow))

                   {

                     modenow=a[k];

                     modeplv=Time[a[k]];

                   }

               }

             mode[i][j]=modenow;

             mplv[i][j]=modeplv;

           }

       } memset(Time,,sizeof(Time));

 }

 int Getplv(const int &v,const int &L,const int &R){return plv[v][R]-plv[v][L-];}

 int main()

 {

     n=G(); m=G();

     for(int i=;i<=n;i++) {b[i].v=G(); b[i].p=i;}

     makeblock(); LiSan(); makeplv(); makemode();

     for(int i=;i<=m;i++)

       {

         x=G(); y=G(); x=(x+ans-)%n+; y=(y+ans-)%n+;

         if(x>y) swap(x,y);

         int modenow,modeplv=;

         if(num[x]+>=num[y])

           {

             for(int j=x;j<=y;j++)

               {

                 Time[a[j]]++;

                 if(Time[a[j]]>modeplv||(Time[a[j]]==modeplv&&a[j]<modenow))

                   {

                     modenow=a[j];

                     modeplv=Time[a[j]];

                   }

               }

             for(int j=x;j<=y;j++) Time[a[j]]--;

           }

         else

           {

             modenow=mode[num[x]+][num[y]-];

             modeplv=mplv[num[x]+][num[y]-];

             for(int j=x;j<=r[num[x]];j++)

               {

                 Time[a[j]]++; int t=Time[a[j]]+Getplv(a[j],num[x]+,num[y]-);

                 if(t>modeplv||(t==modeplv&&a[j]<modenow))

                   {

                     modenow=a[j];

                     modeplv=t;

                   }

               }

             for(int j=l[num[y]];j<=y;j++)

               {

                 Time[a[j]]++; int t=Time[a[j]]+Getplv(a[j],num[x]+,num[y]-);

                 if(t>modeplv||(t==modeplv&&a[j]<modenow))

                   {

                     modenow=a[j];

                     modeplv=t;

                   }

               }

             for(int j=x;j<=r[num[x]];j++) Time[a[j]]--;

             for(int j=l[num[y]];j<=y;j++) Time[a[j]]--;

           }

         P(ans=ma[modenow]);

       }

     return ;

 }