第一行两个整数n,m，表示有n株蒲公英，m次询问。
接下来一行 n 个空格分隔的整数ai，表示蒲公英的种类
再接下来m行每行两个整数l0,r0,我们令上次询问的结果为x（如果这是第一次询问，则x=0)。
令l=(l0+x-1)mod n +1,r=(r0+x-1)mod n +1,如果l>r，则交换l,r。

最终的询问区间为[l,r]。

输出m行。每行一个整数，表示每次询问的结果。

样例输入

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

const int N=;

const int SQRTN=;

const int INF=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

int n,m,lim,s,cnt,a[N],b[N],bl[SQRTN],br[SQRTN];

int sum[N][SQRTN],ans[N][SQRTN],t[N];

bool vis[N];

inline void LSH(){

    sort(b+,b+lim+);

    lim=unique(b+,b+lim+)-b-;

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

        a[i]=lower_bound(b+,b+lim+,a[i])-b;

    }

    return;

}

inline void intoblock(){

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

        if(i%s==){br[cnt]=i-;bl[++cnt]=i;}

    }

    br[cnt]=n;bl[cnt+]=n+;

    return;

}

inline void init(){

    for(int i=;i<=cnt;i++){

        for(int j=bl[i];j<=n;j++)t[a[j]]=;

        int maxn=-INF,cur;

        for(int j=i;j<=cnt;j++){

            for(int k=bl[j];k<=br[j];k++){

                int c=++t[a[k]];

                if(c>maxn)maxn=c,cur=a[k];

                else if(c==maxn&&a[k]<cur)cur=a[k];

            }

            ans[i][j]=cur;

        }

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

        for(int j=bl[i];j<=br[i];j++){

            sum[a[j]][i]++;

        }

    }

    return;

}

inline int query(int l,int r){

    memset(vis,,sizeof(vis));

    memset(t,,sizeof(t));

    int maxn=-INF,cur;

    if(r-l+<=*s){

        for(int i=l;i<=r;i++){

            vis[a[i]]=;

            t[a[i]]++;

        }

        for(int i=l;i<=r;i++){

            if(vis[a[i]]){

                if(t[a[i]]>maxn)maxn=t[a[i]],cur=a[i];

                else if(t[a[i]]==maxn&&a[i]<cur)cur=a[i];

            }

        }

        return cur;

    }

    int L=(l-)/s+,R=(r-)/s+;

    cur=ans[L+][R-];

    maxn=sum[cur][R-]-sum[cur][L];

    for(int i=l;i<=br[L];i++){

        vis[a[i]]=;

        t[a[i]]++;

    }

    for(int i=bl[R];i<=r;i++){

        vis[a[i]]=;

        t[a[i]]++;

    }

    for(int i=l;i<=br[L];i++){

        if(vis[a[i]]){

            int c=t[a[i]]+sum[a[i]][R-]-sum[a[i]][L];

            if(c>maxn)maxn=c,cur=a[i];

            else if(c==maxn&&a[i]<cur)cur=a[i];

        }

    }

    for(int i=bl[R];i<=r;i++){

        if(vis[a[i]]){

            int c=t[a[i]]+sum[a[i]][R-]-sum[a[i]][L];

            if(c>maxn)maxn=c,cur=a[i];

            else if(c==maxn&&a[i]<cur)cur=a[i];

        }

    }

    return cur;

}

int main(){

    n=read();m=read();s=sqrt(n);

    for(int i=;i<=n;i++)a[i]=b[++lim]=read();

    LSH();

    intoblock();

    init();

    int pre=;

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

        int l=(read()+pre-)%n+,r=(read()+pre-)%n+;

        if(l>r)swap(l,r);

        printf("%d\n",pre=b[query(l,r)]);

    }

    return ;

}