#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

int b[],a[],n,m,lon,pos[],t,p[],back[],num[],f[][],sz;

int cmp(const int x,const int y)

{

    if(b[x]<b[y])return ;

    if(b[x]==b[y]&&x<y)return ;

    return ;

}

vector<int> place[];

inline void do_it(int x)

{

    memset(num,,sizeof(num));

    int who=,how=;

    for(int i=(x-)*lon+;i<=n;i++)

    {

      num[a[i]]++;

      if(num[a[i]]>how||(num[a[i]]==how&&back[a[i]]<back[who]))

        who=a[i],how=num[a[i]];

      f[x][pos[i]]=who;

    }

}

inline void Init()

{

    scanf("%d%d",&n,&m);

    lon=(int)sqrt(n+0.5);

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

    {

      scanf("%d",&b[i]);

      p[i]=i;

      pos[i]=(i-)/lon+;

    }

    sort(p+,p+n+,cmp);

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

    {

      if(b[p[i]]!=b[p[i-]])

      {

        a[p[i]]=++sz;

        back[sz]=b[p[i]];

      }

      else

        a[p[i]]=sz;

      place[sz].push_back(p[i]);

    }

    t=pos[n];

    for(int i=;i<=t;i++)do_it(i);

}

inline int query(int l,int r,int x)

{

    return upper_bound(place[x].begin(),place[x].end(),r)-lower_bound(place[x].begin(),place[x].end(),l);

}

inline int Min(int x,int y){return x<y?x:y;}

inline int work(int l,int r)

{

    int z=pos[l]+,y=pos[r]-;

    int who=f[z][y],how=query(l,r,who);

    int zzh=(z-)*lon;

    zzh=Min(zzh,r);

    for(int i=l;i<=zzh;i++)

    {

      int x=query(l,r,a[i]);

      if(x>how||(x==how&&a[i]<who))

         who=a[i],how=x;

    }

    if(pos[l]!=pos[r])

    {

        zzh=(y*lon)+;

        for(int i=zzh;i<=r;i++)

        {

          int x=query(l,r,a[i]);

          if(x>how||(x==how&&a[i]<who))

             who=a[i],how=x;

        }

    }

    return back[who];

}

int main()

{

    Init();

    int k=;

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

    {

       int x,y;

       scanf("%d%d",&x,&y);

       x=(x+k-)%n+;

       y=(y+k-)%n+;

       if(x>y)x^=y^=x^=y;

       k=work(x,y);

       printf("%d\n",k);

    }

    return ;

}