rt

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=2e2+10;
int n,m;
int a[N],b[N];
int bel[N],lx[N],rx[N],cnt,B;
int sum;
int s[M][N],p[M][M];
int t[N];
signed main()
{
	cin>>n>>m;B=sqrt(n);
	for(int i=1;i<=n;i++)
		cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	sum=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+sum+1,a[i])-b;
	for(int i=1,j;i<=n;i=j+1)
	{
		j=min(n,i+B-1);
		lx[++cnt]=i;rx[cnt]=j;
		for(int ii=i;ii<=j;ii++)
			bel[ii]=cnt;
	}
	for(int i=1;i<=n;i++)
		s[bel[i]][a[i]]++;
	for(int i=1;i<=cnt;i++)
		for(int j=0;j<=sum;j++)
			s[i][j]+=s[i-1][j];
	for(int i=1;i<=cnt;i++)
		for(int j=i;j<=cnt;j++)
		{
			int ans=p[i][j-1];
			for(int k=lx[j];k<=rx[j];k++)
				if((s[j][a[k]]-s[i-1][a[k]]>s[j][ans]-s[i-1][ans])||(s[j][a[k]]-s[i-1][a[k]]==s[j][ans]-s[i-1][ans]&&a[k]<ans))
					ans=a[k];
			p[i][j]=ans;
		}
	int res=0;
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		l=(l+res-1)%n+1;
		r=(r+res-1)%n+1;
		if(l>r)swap(l,r);
		int mx=0;
		if(bel[r]-bel[l]<=1)
		{
			
			for(int i=l;i<=r;i++)
				t[a[i]]++;
			for(int i=l;i<=r;i++)	
				if(t[a[i]]>t[mx]||(t[a[i]]==mx&&a[i]<mx))
					mx=a[i];
			for(int i=l;i<=r;i++)
				t[a[i]]=0;
		}
		else
		{
			mx=p[bel[l]+1][bel[r]-1];
			for(int i=l;i<=rx[bel[l]];i++)t[a[i]]++;
			for(int i=lx[bel[r]];i<=r;i++)t[a[i]]++;
			for(int i=l;i<=rx[bel[l]];i++)
			{
				int ans=t[mx]+s[bel[r]-1][mx]-s[bel[l]][mx];
				int now=t[a[i]]+s[bel[r]-1][a[i]]-s[bel[l]][a[i]];
				if(now>ans||(now==ans&&a[i]<mx))
					mx=a[i];
			}
			for(int i=lx[bel[r]];i<=r;i++)
			{
				int ans=t[mx]+s[bel[r]-1][mx]-s[bel[l]][mx];
				int now=t[a[i]]+s[bel[r]-1][a[i]]-s[bel[l]][a[i]];
				if(now>ans||(now==ans&&a[i]<mx))
					mx=a[i];
			}
			for(int i=l;i<=rx[bel[l]];i++)t[a[i]]=0;
			for(int i=lx[bel[r]];i<=r;i++)t[a[i]]=0;
		}
		res=b[mx];
		cout<<res<<endl;
	}
	return 0;
}