rt

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+5,sqrtn=205;
int n,m,b[maxn],a[maxn],l[maxn],r[maxn],bk[sqrtn][maxn],t,tbk[sqrtn][maxn],sum[sqrtn][maxn];
struct node
{
    int x,id;
}p[sqrtn][sqrtn];
int query(int x,int y)
{
    int tl=lower_bound(l+1,l+t+1,x)-l,tr=upper_bound(r+1,r+t+1,y)-r-1;
    int bk[maxn],tp[maxn];
    node ma=p[tl][tr];
    memset(bk,0,sizeof bk);
    memset(tp,0,sizeof tp);
    if(y-x+1<=t)
    {
        node ma;
        ma.x=ma.id=0;
        for(int i=x;i<=y;i++)
        {
            // cout<<i<<' '<<a[i]<<endl;
            ++bk[a[i]];
            if(bk[a[i]]>ma.x)
            {
                ma.x=bk[a[i]];
                ma.id=a[i];
            }
            if(bk[a[i]]==ma.x)
            {
                ma.id=min(ma.id,a[i]);
            }
        }
        // cout<<"QEFED"<<ma.x<<endl;
        return ma.id;
    }
    for(int i=x;i<l[tl];i++)
    {
        // cout<<i<<' '<<a[i]<<endl;
        ++bk[a[i]];
        if(!tp[a[i]])
        {
            tp[a[i]]=1;
            bk[a[i]]+=sum[tr][a[i]]-sum[tl-1][a[i]];
            if(bk[a[i]]>ma.x)
            {
                ma.x=bk[a[i]];
                ma.id=a[i];
            }
            if(bk[a[i]]==ma.x)
                ma.id=min(ma.id,a[i]);
        }
    }
    for(int i=r[tr]+1;i<=y;i++)
    {
        ++bk[a[i]];
        if(!tp[a[i]])
        {
            tp[a[i]]=1;
            bk[a[i]]+=sum[tr][a[i]]-sum[tl-1][a[i]];
            // ma=max(ma,bk[a[i]]);
            if(bk[a[i]]>ma.x)
            {
                ma.x=bk[a[i]];
                ma.id=a[i];
            }
            if(bk[a[i]]==ma.x)
                ma.id=min(ma.id,a[i]);
        }
    }
    // cout<<"QUQUQUQ"<<ma.x<<endl;
    return ma.id;
}
void yuchuli()
{   
    int bk[maxn];
    for(int i=1;i<=t;i++)
    {
        for(int j=1;j<=n;j++)
        {
            sum[i][j]=sum[i-1][j];
        }
        for(int k=l[i];k<=r[i];k++)
            ++sum[i][a[k]];
    }
    for(int i=1;i<=t;i++)
    {
        memset(bk,0,sizeof bk);
        node tp;
        tp.x=tp.id=0;
        for(int j=i;j<=t;j++)
        {
            for(int k=l[j];k<=r[j];k++)
            {
                ++bk[a[k]];
                if(bk[a[k]]>tp.x)
                {
                    tp.x=bk[a[k]];
                    tp.id=k;
                }
                if(bk[a[k]]==tp.x)
                    tp.id=min(tp.id,a[k]);
            }
            p[i][j]=tp;
        }
    }
}
int tn,tp[maxn];
int main()
{
    // freopen("qaq.in","r",stdin);
    // freopen("my.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];   
    }
    sort(b+1,b+n+1);
    // cout<<endl;
    tn=unique(b+1,b+n+1)-b-1;
    // for(int i=1;i<=tn;i++)
    //     cout<<b[i]<<' ';
    // cout<<endl;
    for(int i=1;i<=n;i++)
    {
        int k=lower_bound(b+1,b+tn+1,a[i])-b;
        tp[k]=a[i];
        a[i]=k;
        // cout<<a[i]<<endl;
    }
    t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        l[i]=(i-1)*t+1;
        r[i]=i*t;
    }
    if(r[t]<n)
    {
        ++t;
        l[t]=r[t-1]+1;
        r[t]=n;
    }
    // for(int i=1;i<=t;i++)
    //     cout<<"QWQ"<<l[i]<<" "<<r[i]<<endl;
    yuchuli();
    for(int i=1;i<=t;i++)
    {
        for(int j=l[i];j<=r[i];j++)
            ++bk[i][a[j]];
    }
    int las=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        x=(x+las-1)%n+1;
        y=(y+las-1)%n+1;
        // cout<<"QWQ"<<x<<' '<<y<<endl;
        if(x>y)
            swap(x,y);
        las=query(x,y);
        las=tp[las];
        cout<<las<<endl;
    }
    return 0;
}