#include <bits/stdc++.h>
using namespace std;
const int N=4e4+5,M=205;
int n,m,t;
int a[N],p[N];
int z[M][M],s[M][N];
int b[N],bl;
int cnt[N],tmp[N];
//z[i][j]表示i到j块的众数，s[i][j]表示前i个块j数字的出现个数
void pre(){
	for(int i=1;i<=b[n];i++){
		for(int j=1;j<=t;j++)s[i][j]=s[i-1][j];
		for(int j=(i-1)*bl+1;j<=min(n,bl*i);j++)s[i][a[j]]++;
	}
	for(int i=1;i<=b[n];i++){
		int mx=0,num;
		memset(cnt,0,sizeof cnt);
		for(int j=(i-1)*bl+1;j<=n;j++){
			cnt[a[j]]++;
			if(cnt[a[j]]>mx){
				mx=cnt[a[j]];
				num=a[j];
			}else if(cnt[a[j]]==mx&&a[j]<num)num=a[j];
			if(!(j%bl)||j==n)z[i][j/bl]=num;
		}
	}
} 
int ans=0;
int query(int l,int r){
	int lb=(l-1)/bl+1,rb=(r-1)/bl+1;
	if(lb+1>rb-1){
		int mx=0,num;
		for(int i=l;i<=r;i++){
			tmp[a[i]]++;
			if(tmp[a[i]]>mx){
				mx=tmp[a[i]];
				num=a[i];
			}else if(tmp[a[i]]==mx&&a[i]<num)num=a[i];			
		}for(int i=l;i<=r;i++)tmp[a[i]]=0;
		return p[num];
	}
	int num=z[lb+1][rb-1];
	int mx=s[rb-1][num]-s[lb][num];
	for(int i=l;i<=lb*bl;i++){
		tmp[a[i]]++;
		if(tmp[a[i]]+s[rb-1][a[i]]-s[lb][a[i]]>mx){
			mx=tmp[a[i]]+s[rb-1][a[i]]-s[lb][a[i]];
			num=a[i];
		}else if(tmp[a[i]]+s[rb-1][a[i]]-s[lb][a[i]]==mx&&a[i]<num)num=a[i];
	}
	for(int i=(rb-1)*bl+1;i<=r;i++){
		tmp[a[i]]++;
		if(tmp[a[i]]+s[rb-1][a[i]]-s[lb][a[i]]>mx){
			mx=tmp[a[i]]+s[rb-1][a[i]]-s[lb][a[i]];
			num=a[i];
		}else if(tmp[a[i]]+s[rb-1][a[i]]-s[lb][a[i]]==mx&&a[i]<num)num=a[i];
	}
	for(int i=l;i<=lb*bl;i++)tmp[a[i]]=0;
	for(int i=(rb-1)*bl+1;i<=r;i++)tmp[a[i]]=0;
	return p[num];
}
int main(){
	scanf("%d%d",&n,&m);
	bl=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		p[i]=a[i];
		b[i]=(i-1)/bl+1;
	}
	sort(p+1,p+n+1);
	t=unique(p+1,p+n+1)-p-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(p+1,p+t+1,a[i])-p;
	pre();
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;
		if(l>r)swap(l,r);
		printf("%d\n",ans=query(l,r));
	}
	return 0;
}

80pts WA on 1、2、4、5