#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 50010

#define BLOCK 250

int n,m,a[N],b[N],lastans=;

int block,tot,L[N],R[N],pos[N];

int cnt[N],f[BLOCK][BLOCK],sum[BLOCK][N];

int main()

{

    freopen("bzoj2724.in","r",stdin);

    freopen("bzoj2724.out","w",stdout);

    n=read(),m=read();

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

    sort(b+,b+n+);

    int t=unique(b+,b+n+)-b;

    for (int i=;i<=n;i++) a[i]=lower_bound(b+,b+t,a[i])-b;

    block=sqrt(n);tot=n/block+(n%block>);

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

    L[i]=(i-)*block+,R[i]=(i-)*block+block;

    if (n/block<tot) L[tot]=n/block*block+,R[tot]=n;

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

    {

        memset(cnt,,sizeof(cnt));

        int num=;

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

        {

            for (int k=L[j];k<=R[j];k++)

            {

                cnt[a[k]]++;

                if (cnt[a[k]]>cnt[num]||cnt[a[k]]==cnt[num]&&a[k]<num) num=a[k];

            }

            f[i][j]=num;

        }

        memcpy(sum[i],sum[i-],sizeof(sum[i]));

        for (int j=L[i];j<=R[i];j++)

        pos[j]=i,sum[i][a[j]]++;

    }

    memset(cnt,,sizeof(cnt));

    while (m--)

    {

        int x=read(),y=read();

        x=(x+lastans-)%n+,y=(y+lastans-)%n+;

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

        int num=;

        if (pos[x]==pos[y])

        {

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

            {

                cnt[a[i]]++;

                if (cnt[a[i]]>cnt[num]||cnt[a[i]]==cnt[num]&&a[i]<num) num=a[i];

            }

            for (int i=x;i<=y;i++) cnt[a[i]]--;

        }

        else

        {

            num=f[pos[x]+][pos[y]-];

            for (int i=x;i<=R[pos[x]];i++)

            {

                cnt[a[i]]++;

                if (cnt[a[i]]+sum[pos[y]-][a[i]]-sum[pos[x]][a[i]]>cnt[num]+sum[pos[y]-][num]-sum[pos[x]][num]

                ||cnt[a[i]]+sum[pos[y]-][a[i]]-sum[pos[x]][a[i]]==cnt[num]+sum[pos[y]-][num]-sum[pos[x]][num]&&a[i]<num)

                num=a[i];

            }

            for (int i=L[pos[y]];i<=y;i++)

            {

                cnt[a[i]]++;

                if (cnt[a[i]]+sum[pos[y]-][a[i]]-sum[pos[x]][a[i]]>cnt[num]+sum[pos[y]-][num]-sum[pos[x]][num]

                ||cnt[a[i]]+sum[pos[y]-][a[i]]-sum[pos[x]][a[i]]==cnt[num]+sum[pos[y]-][num]-sum[pos[x]][num]&&a[i]<num)

                num=a[i];

            }

            for (int i=x;i<=R[pos[x]];i++) cnt[a[i]]--;

            for (int i=L[pos[y]];i<=y;i++) cnt[a[i]]--;

        }

        lastans=b[num];

        printf("%d\n",b[num]);

    }

    fclose(stdin);fclose(stdout);

    return ;

}