#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=40010;
const ll maxx=2323237;
int x[maxx],y[maxx],num,ans=0;
void hash(int a,int v)
{
	ll temp=a;
	while(y[temp]!=0&&y[temp]!=a)	temp=(temp*1519+7)%maxx;
	y[temp]=a,x[temp]+=v;
	if(x[temp]>num||(num==x[temp]&&ans>a))	num=x[temp],ans=a;
}
int n,m;
int a[maxn];
void work1()
{
	int l,r;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		int L=(l+ans-1)%n+1,R=(r+ans-1)%n+1;
		if(L>R)	swap(L,R);
		for(int i=L;i<=R;i++)
			hash(a[i],1);
		printf("%d\n",ans);
		for(int i=L;i<=R;i++)
			hash(a[i],-1);
		num=0;
	}
}
struct my
{
	int v,x;
}b[maxn];
bool cm(my a,my b){	return a.v<b.v;}
bool cm2(my a,my b){return a.x<b.x;}
int c[210][maxn],d[maxn],h[210][210],shu[210];
void work2()
{
	int unit=(int)sqrt(n*1.0);
	for(int i=1;i<=n;i++)	b[i].v=a[i],b[i].x=i;
	sort(a+1,a+1+n);
	sort(b+1,b+1+n,cm);
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=a[i-1])	{	num++;	d[num]=a[i];}
		b[i].v=num;
	}
	sort(b+1,b+1+n,cm2);
	int k=1;
	while(k*unit<n)
	{
		for(int i=(k-1)*unit+1;i<=k*unit;i++)
		{	
			if(c[k][b[i].v]==0)	shu[k]++,h[k][shu[k]]=b[i].v;
			c[k][b[i].v]++;
		}
		k++;
	}
	for(int i=(k-1)*unit+1;i<=n;i++)
	{	
		if(c[k][b[i].v]==0)	shu[k]++,h[k][shu[k]]=b[i].v;
		c[k][b[i].v]++;
	}

	int l,r;
	for(int z=1;z<=m;z++)
	{
		scanf("%d%d",&l,&r);
		int L=(l+d[ans]-1)%n+1,R=(r+d[ans]-1)%n+1;
		if(L>R)	swap(L,R);
		int s[maxn]={},A=0,i=1;
		while(i*unit<L)	i++;
		for(int j=L;j<=min(i*unit,R);j++)
		{	
			s[b[j].v]++;
			if(s[b[j].v]>A||(s[b[j].v]==A&&b[j].v<ans))	
				A=s[b[j].v],ans=b[j].v;
		}
		i++;
		while(i*unit<=R)
		{
			for(int j=1;j<=shu[i];j++)
				{	
					s[h[i][j]]+=c[i][h[i][j]];
					if(s[h[i][j]]>A||(s[h[i][j]]==A&&h[i][j]<ans))	
						A=s[h[i][j]],ans=h[i][j];
				}
			i++;
		}
		if(i*unit-unit>L)
		for(int j=i*unit-unit+1;j<=R;j++)
		{	
			s[b[j].v]++;
			if(s[b[j].v]>A||(s[b[j].v]==A&&b[j].v<ans))
				A=s[b[j].v],ans=b[j].v;
		}
		printf("%d\n",d[ans]);
	}
}
int main()
{
	freopen("numquery.in","r",stdin);
	freopen("numquery.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	if(n<=10000)	work1();
	else	
		work2();
	return 0;
}