#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
#include<vector>
using namespace std;
int n,m,bl,c;
int a[40010];
int hs[40010];
int bk[40010];
int bc[40010];
vector<int>v[400010];
map<int,int>d;
int main()
{
    //freopen("P4168_1.in","r",stdin);
    cin>>n>>m;
    bl=sqrt(n);
    int mx=0,x=0,u,w;
    hs[0]=(1<<30)+(1<<29);
    v[0].push_back((1<<30)+(1<<29));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i%bl==1)
        {
            fill(bc,bc+c+1,0);
            bk[i/bl]=x;
            mx=0;
        }
        if(!d[a[i]])
        {
            d[a[i]]=++c;
            hs[c]=a[i];
        }
        u=d[a[i]];
        v[u].push_back(i);
        bc[u]++;
        if(bc[u]>mx||bc[u]==mx&&a[i]<hs[x])
        {
            mx=bc[u];
            x=u;
        }
    }
    bk[(n+bl-1)/bl]=x;
    for(int i=1;i<=c;i++)
    {
        v[i].push_back((1<<30));
    }
    int l,r;
    x=0;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        mx=0;
        l=(l+x-1)%n+1;
        r=(r+x-1)%n+1;
        if(l>r)
        {
            swap(l,r);
        }
        //cout<<l<<' '<<r<<endl;
        x=0;
        for(int j=l/bl;j<=r/bl;j++)
        {
            u=lower_bound(v[bk[j]].begin(),v[bk[j]].end(),l)-v[bk[j]].begin();
            w=upper_bound(v[bk[j]].begin(),v[bk[j]].end(),r)-v[bk[j]].begin();
            if(w-u>mx||w-u==mx&&hs[bk[j]]<hs[x])
            {
                mx=w-u;
                x=bk[j];
            }
        }
        for(int j=l;j<=(l+bl)/bl*bl&&j<=n;j++)
        {
            int tmp=d[a[j]];
            u=lower_bound(v[tmp].begin(),v[tmp].end(),l)-v[tmp].begin();
            w=upper_bound(v[tmp].begin(),v[tmp].end(),r)-v[tmp].begin();
            if(w-u>mx||w-u==mx&&hs[tmp]<hs[x])
            {
                mx=w-u;
                x=tmp;
            }
        }
        for(int j=r/bl*bl;j<=r;j++)
        {
            int tmp=d[a[j]];
            u=lower_bound(v[tmp].begin(),v[tmp].end(),l)-v[tmp].begin();
            w=upper_bound(v[tmp].begin(),v[tmp].end(),r)-v[tmp].begin();
            if(w-u>mx||w-u==mx&&hs[tmp]<hs[x])
            {
                mx=w-u;
                x=tmp;
            }
        }
        x=hs[x];
        cout<<x<<endl;
    }
    return 0;
}