#include<bits/stdc++.h>
using namespace std;
const int N=250;
const int M=40005;
int n,m,k;
int cnt[N][M];
int f[N][N];
int g[N][N];
int a[M];
int b[M];
int v[M];
int bel[M];
int num[M];
int query(int l,int r){
	int ans=0,mx=0,sum;
	ans=f[bel[l]+1][bel[r]-1];
	mx=g[bel[l]+1][bel[r]-1];
	memset(num,0,sizeof(num));
	for (int i=l;i<=min(bel[l]*k,r);i++)num[a[i]]++;
	for (int i=max(l,(bel[r]-1)*k+1);i<=r;i++)num[a[i]]++;
	for (int i=l;i<=min(bel[l]*k,r);i++){
			sum=num[a[i]]+cnt[bel[r]-1][a[i]]-cnt[bel[l]][a[i]];
		if (sum>mx||(sum==mx&&a[i]<ans))mx=sum,ans=a[i];
	}
	for (int i=max(l,(bel[r]-1)*k+1);i<=r;i++){
		if (bel[l]==bel[r]){
			sum=num[a[i]];
		}
		else{
			sum=num[a[i]]+cnt[bel[r]-1][a[i]]-cnt[bel[l]][a[i]];
		}
		if (sum>mx||(sum==mx&&a[i]<ans))mx=sum,ans=a[i];
	}
	return ans;
}
int main(){
	scanf ("%d %d",&n,&m);
	k=(int)sqrt(n);
	int s=n;
	for (int i=1;i<=n;i++)bel[i]=(i-1)/k+1;
	for (int i=1;i<=n;i++){scanf ("%d",&a[i]);b[i]=a[i];}
	sort (b+1,b+n+1);
	n=unique(b+1,b+n+1)-b-1;
	for (int i=1;i<=n;i++){
		int pos=lower_bound(b+1,b+n+1,a[i])-b;
		v[pos]=a[i];
		a[i]=pos;
	}
	n=s;
	for (int i=1;i<=n;i++){
		num[a[i]]++;
		if (i==bel[i]*k||i==n)memcpy(cnt[bel[i]],num,sizeof(num));
	}
	for (int j=1;j<=bel[n];j++){
		memset(num,0,sizeof(num));
		int ans=0,mx=0;
		for (int i=(j-1)*k+1;i<=n;i++){
			num[a[i]]++;        
			int y=bel[i];
			if (num[a[i]]>mx || (num[a[i]]==mx && a[i]<ans)) ans=a[i],mx=num[a[i]];
			f[j][y]=ans;
			g[j][y]=mx;
		}
	}
	int ans=0,L,R;
	while(m--){
		scanf ("%d %d",&L,&R);
		L=(L+ans-1)%n+1;
		R=(R+ans-1)%n+1;
		if (L>R)swap(L,R);
		ans=v[query(L,R)];
		printf ("%d\n",ans);
	}
	return 0;
}