#include<bits/stdc++.h>
using namespace std;
int n,m,la,t,len,nn;
long long ls3,ls4,bh,ans,ls;
int a[40010],l[210],r[210],b[40010];
long long cnt[40010];
int pos[40010],yuan[40010];
int f[210][210];
long long s[210][40010];
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];		
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	nn=unique(b+1,b+1+n)-(b+1);
	for(int i=1,ls1;i<=n;i++)
	{
		ls1=lower_bound(b+1,b+1+nn,a[i])-b;
		yuan[ls1]=b[ls1];
		a[i]=ls1;
		
	}
	t=sqrt(n);
	len=t;
	for(int i=1;i<=t;i++)
	{
		l[i]=(i-1)*len+1;
		r[i]=i*len;
	}
	if(r[t]<n)
	{
		t++;
		l[t]=r[t-1]+1;
		r[t]=n;
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=l[i];j<=r[i];j++)
		{
			s[i][a[j]]++;
		}
		for(int j=1;j<=nn+1;j++)
		{
			s[i][j]+=s[i-1][j];
		}
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=i;j<=t;j++)
		{//i--->j
			bh=f[i][j-1];
			for(int k=l[j];k<=r[j];k++)
			{
				
				if(s[j][a[k]]-s[i-1][a[k]]>s[j][bh]-s[i-1][bh])
				{
					bh=a[k];
				}
				if(s[j][a[k]]-s[i-1][a[k]]==s[j][bh]-s[i-1][bh])
				{
					if(a[k]<bh)
					{
						bh=a[k];
					}
				}
			}
			f[i][j]=bh;
		}
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=l[i];j<=r[i];j++)
		{
			pos[j]=i;
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>ls3>>ls4;
		ls3=(ls3+la-1)%n+1;
		ls4=(ls4+la-1)%n+1;
		if(ls3>ls4)
		{
			swap(ls3,ls4);
		}
		if(pos[ls4]-pos[ls3]<=3)
		{
			ans=-1;
			for(int j=ls3;j<=ls4;j++)
			{
				cnt[a[j]]++;
				if(ans==-1)
				{
					ans=cnt[a[j]];
					bh=a[j];
				}
				if(cnt[a[j]]>ans)
				{
					ans=cnt[a[j]];
					bh=a[j];
				}
				if(cnt[a[j]]==ans)
				{
					if(a[j]<bh)
					{
						ans=cnt[a[j]];
						bh=a[j];
					}
				}
			}
			for(int j=ls3;j<=ls4;j++)
			{
				cnt[a[j]]=0;
			}
			printf("%d\n",yuan[bh]);
			la=yuan[bh];
		}
		else
		{
			
			bh=f[pos[ls3]+1][pos[ls4]-1];
			ans=s[pos[ls4]-1][bh]-s[pos[ls3]][bh];
			for(int j=ls3;j<=r[pos[ls3]];j++)
			{
				cnt[a[j]]++;
			}
			for(int j=ls4;j>=l[pos[ls4]];j--)
			{
				cnt[a[j]]++;
			}
			ans+=cnt[bh];
			for(int j=ls3;j<=r[pos[ls3]];j++)
			{
				ls=cnt[a[j]]+s[pos[ls4]-1][a[j]]-s[pos[ls3]][a[j]];
				if(ls>ans)
				{
					ans=ls;
				}
				if(ls==ans)
				{
					if(a[j]<bh)
					{
						bh=a[j];
					}
				}
			}
			for(int j=ls4;j>=l[pos[ls4]];j--)
			{
				ls=cnt[a[j]]+s[pos[ls4]-1][a[j]]-s[pos[ls3]][a[j]];
				if(ls>ans)
				{
					ans=ls;
				}
				if(ls==ans)
				{
					if(a[j]<bh)
					{
						bh=a[j];
					}
				}
			}
			for(int j=ls3;j<=r[pos[ls3]];j++)
			{
				cnt[a[j]]=0;
			}
			for(int j=ls4;j>=l[pos[ls4]];j--)
			{
				cnt[a[j]]=0;
			}
			printf("%d\n",yuan[bh]);
			la=yuan[bh];
		}
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

yuan数组存离散前的值

f[i][j]表示从第i个块到第j个块的众数是几

s[i][k]表示前i个块中a[k]有几个