#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=40050;
const int len=3005;
int n,m;
int st[len];
int ed[len];
struct numb
{
	int v;
	int bh;
	int wz;
};
numb a[maxn];
int b[maxn];
int pos[maxn];
int t1[len+5][maxn];
int zs[len][len];
int zss[len];
int css[len];
int c[maxn];
int cs[len][len];
bool mycmp(numb a,numb b)
{
	return a.v<b.v;
}
inline void myswap(int &x,int &y)
{
	int t=y;
	y=x;
	x=t;
	return;
}
int query(int l,int r)
{
	int cx[maxn]={};
	int te[maxn]={};
	int tte=0;
	if(pos[l]+1==pos[r]||pos[l]==pos[r])
	{
		int tzs=0,tcs=0;
		for(int i=l;i<=r;i++)
		{
			cx[b[i]]++;
			if(cx[b[i]]>tcs)
			{
				tcs=cx[b[i]];
				tzs=b[i];
			}
			else if(cx[b[i]]==tcs)
			{
				tzs=min(b[i],tzs);
			}
		}
		printf("%d\n",c[tzs]);
		return c[tzs];
	}
	else 
	{
		int L=(pos[l])*len;
		int R=(pos[r]-1)*len-1;
		for(int i=l;i<=L-1;i++)
		{
			cx[b[i]]++;
			if(cx[b[i]]==1)
				te[++tte]=b[i];
		}
		for(int i=R+1;i<=r;i++)
		{
			cx[b[i]]++;
			if(cx[b[i]]==1)
				te[++tte]=b[i];
		}
		int tcs=cs[L][R];
		int tzs=zs[L][R];
		for(int i=1;i<=tte;i++)
		{
			if(t1[R][te[i]]-t1[L-1][te[i]]+cx[te[i]]>tcs)
			{
				tcs=t1[R][te[i]]-t1[L-1][te[i]]+cx[te[i]];
				tzs=te[i];
			}
		}
		printf("%d\n",c[tzs]);
		return c[tzs];
	}
}
bool mycmp2(numb aa,numb bb)
{
	return aa.wz<bb.wz;
}
int main()
{
	freopen("numquery.in","r",stdin);
	freopen("numquery.in","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].v);
		a[i].bh=i;
	}
	sort(a+1,a+n+1,mycmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i].v!=a[i-1].v)
		{
			b[a[i].bh]=b[a[i-1].bh]+1;
			c[b[a[i-1].bh]+1]=a[i].v;
		}
		else
		{
			b[a[i].bh]=b[a[i-1].bh];
			c[b[a[i-1].bh]]=a[i].v;
		}
	}
	int t=1;//[0,len-1][len,(2*len-1)]
	for(int i=1;i<=n;i++)
	{
		if(i/len==(i-1)/len)
		{
			pos[i]=t;
		}
		else 
			pos[i]=++t;
	}
	for(int i=1;i<=len;i++)
	{	
		int hh[maxn]={};
		for(int j=i;j<=len;j++)
		{
			for(int k=st[j];k<=ed[j];k++)
			{
				hh[b[k]]++;
				if(cs[i][j]<hh[b[k]])
				{
					zs[i][j]=b[k];
					cs[i][j]=hh[b[k]];
				}
				else if(cs[i][j]==hh[b[k]])
				{
					zs[i][j]=min(b[k],zs[i][j]);
				}
			}
		}
	}
	int de=0;
	for(int i=1;i<=m;i++)
	{
		int L,R;
		scanf("%d %d",&L,&R);
		L=(L+de-1)%n+1;
		R=(R+de-1)%n+1;
		if(L>R)
			myswap(L,R);
		de=query(L,R);
	}
	//搞了两个小时分块啊！！！！！代码炸掉没保存一个关键函数，瞬间20分！！GTMD
}