#include<bits/stdc++.h>
using namespace std;
const int N=40005,M=205;
int sum[M][N],pans[M][M];
int n,m;
int a[N],b[N],bk;
//17:05
int st[M],ed[M],pos[N],block;
int vis[N];
bool book[N];
int ask(int l,int r){
	int bl=pos[l],br=pos[r];
	if(bl==br){
		int num=0,p;
		for(int i=l;i<=r;i++)vis[a[i]]=0;
		for(int i=l;i<=r;i++){
			vis[a[i]]++;
			if(vis[a[i]]>num||(vis[a[i]]==num&&a[i]<p)){
				num=vis[a[i]];
				p=a[i];
			}
		}
		return b[p];
	}
	int num=0,p;
	for(int i=l;i<=ed[bl];i++){
		book[a[i]]=vis[a[i]]=0;
	}
	for(int i=st[br];i<=r;i++){
		book[a[i]]=vis[a[i]]=0;
	}
	for(int i=l;i<=ed[bl];i++){
		vis[a[i]]++;
		if(!book[a[i]]){
			vis[a[i]]+=sum[br-1][a[i]]-sum[bl][a[i]];
			book[a[i]]=1;
		}
		if(vis[a[i]]>num||(vis[a[i]]==num&&a[i]<p)){
			num=vis[a[i]];
			p=a[i];
		}
	}
	for(int i=st[br];i<=r;i++){
		vis[a[i]]++;
		if(!book[a[i]]){
			vis[a[i]]+=sum[br-1][a[i]]-sum[bl][a[i]];
			book[a[i]]=1;
		}
		if(vis[a[i]]>num||(vis[a[i]]==num&&a[i]<p)){
			num=vis[a[i]];
			p=a[i];
		}
	}
	int x=pans[bl+1][br-1],y=vis[x];
	if(y>num||(y==num&&x<p)){
		p=x;
	}
	return b[p];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	bk=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+1+bk,a[i])-b;
	}
	block=sqrt(n);
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++){
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
	ed[t]=n;
	for(int i=1;i<=n;i++){
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=t;i++){
		for(int j=1;j<=n;j++){
			sum[i][a[j]]=sum[i-1][a[j]];
		}
		for(int j=st[i];j<=ed[i];j++){
			sum[i][a[j]]++;
		}
	}
	for(int i=1;i<=t;i++){
		memset(vis,0,sizeof(vis));
		int ans=0,p=0;
		for(int j=i;j<=t;j++){
			for(int k=st[j];k<=ed[j];k++){
				vis[a[k]]++;
				if((vis[a[k]]>ans)||(vis[a[k]]==ans&&a[k]<p)){
					ans=vis[a[k]];
					p=a[k];
				}
			}
			pans[i][j]=p;
		}
	}
	int l,r,pre=0;
	while(m--){
		scanf("%d%d",&l,&r);
		l=(l+pre-1)%n+1;
		r=(r+pre-1)%n+1;
		if(l>r)swap(l,r);
		pre=ask(l,r);
		printf("%d\n",pre);
	}
	return 0;
}