#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=4e4+5;
const int maxm=205;
int a[maxn],raw[maxn],pos[maxn],posl[maxm],posr[maxm],Cnt[maxn],cnt[maxm][maxn],ans[maxm][maxn],n,m,p,lastans;
vector<int>v[maxn];
int binary_search(int ver,int Pos){
	int l=1,r=v[ver].size()+1;
	while(l<r){
		int mid=l+r>>1;
		if(v[ver][mid-1]>Pos) r=mid;
		else l=mid+1; 
	}
	return l-1;
}
void prework(){
	sort(raw+1,raw+n+1);
	int len=unique(raw+1,raw+n+1)-raw-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(raw+1,raw+len+1,a[i])-raw;
		v[a[i]].push_back(i);
	}
	pos[n+1]=pos[n]+1;
	for(int i=1;i<=n+1;i++){
		if(pos[i]!=pos[i-1]){
			posl[pos[i]]=i;
			posr[pos[i-1]]=i-1;
		}
	}
	for(int i=1;i<=pos[n];i++){
		int L=posl[i];
		for(int j=L;j<=n;j++){
			Cnt[a[j]]++;
			if(Cnt[a[j]]>Cnt[ans[i][j]])
				ans[i][j]=j;
			if(Cnt[a[j]]==Cnt[ans[i][j]]&&a[j]<a[ans[i][j]])
				ans[i][j]=j;
			cnt[i][j]=Cnt[ans[i][j]];
		}
		for(int j=L;j<=n;j++) Cnt[a[j]]--;
	}
}
int query(int l,int r){
	int val=0,value=0;
	for(int i=l;i<=min(r,posr[pos[l]]);i++){
		int R=binary_search(a[i],r);
		int L=lower_bound(v[a[i]].begin(),v[a[i]].end(),l)-v[a[i]].begin()+1;
		int t=R-L+1;
		if(t>value){
			value=t;
			val=a[i];
		}
		if(t==value&&a[i]<val) val=a[i];
	}
	if(pos[l]==pos[r]) return raw[val];
	for(int i=posl[pos[r]];i<=r;i++){
		int R=binary_search(a[i],r);
		int L=lower_bound(v[a[i]].begin(),v[a[i]].end(),l)-v[a[i]].begin()+1;
		int t=R-L+1;
		if(t>value){
			value=t;
			val=a[i];
		}
		if(t==value&&a[i]<val) val=a[i];
	}
	if(cnt[pos[l]+1][posr[pos[r]-1]]>value){
		value=cnt[pos[l]+1][posr[pos[r]-1]];
		val=a[ans[pos[l]+1][posr[pos[r]-1]]];
	}
	if(cnt[pos[l]+1][posr[pos[r]-1]]==value&&a[ans[pos[l]+1][posr[pos[r]-1]]]<val)
		val=a[ans[pos[l]+1][posr[pos[r]-1]]];
	return raw[val];
}
int main(){
	scanf("%d%d",&n,&m);
	p=max((int)sqrt(n),1);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		raw[i]=a[i];
		pos[i]=(i-1)/p+1;
	}
	prework();
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		l=(l+lastans-1)%n+1,r=(r+lastans-1)%n+1;
		if(l>r) swap(l,r);
		lastans=query(l,r);
		printf("%d\n",lastans);
	}
	return 0;
}