#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4*1e4+10,B=2*1e2+10;
int n,m;
int cnt[B][N],cnt2[B][B]//cnt前i个块j的个数，cnt2第i个块到第j个块的众数 
,LL[B],RR[B],pos[N],d[N];
int a[N],b[N],h[N];
int query(int l,int r){
	int p=pos[l],q=pos[r];
	int mx;
	if(p==q){
		for(int i=l;i<=r;i++){
			h[b[i]]++;
		}
		mx=0;
		for(int i=l;i<=r;i++){
			if(h[b[i]]>h[mx]||h[b[i]]==h[mx]&&b[i]<mx){
				mx=b[i];
			}
		}
		for(int i=l;i<=r;i++){
			h[b[i]]=0;
		}
		return a[mx];
	}
	else{
		mx=cnt2[p+1][q-1];
		for(int i=l;i<=RR[p];i++){
			h[b[i]]++;
		}
		for(int i=LL[q];i<=r;i++){
			h[b[i]]++;
		}
		//
		for(int i=l;i<=RR[p];i++){
			if(h[b[i]]+cnt[q-1][b[i]]-cnt[p][b[i]]>h[mx]+cnt[q-1][mx]-cnt[p][mx]
			||(h[b[i]]+cnt[q-1][b[i]]-cnt[p][b[i]]==h[mx]+cnt[q-1][mx]-cnt[p][mx]&&b[i]<mx)){
				mx=b[i];
			}
		}
		//
		for(int i=LL[q];i<=r;i++){
			if(h[b[i]]+cnt[q-1][b[i]]-cnt[p][b[i]]>h[mx]+cnt[q-1][mx]-cnt[p][mx]
			||(h[b[i]]+cnt[q-1][b[i]]-cnt[p][b[i]]==h[mx]+cnt[q-1][mx]-cnt[p][mx]&&b[i]<mx)){
				mx=b[i];
			}
		}
		//
		for(int i=l;i<=RR[p];i++){
			h[b[i]]=0;
		}
		for(int i=LL[q];i<=r;i++){
			h[b[i]]=0;
		}
	}
	return a[mx];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(a+1,a+1+n);
	int len=unique(a+1,a+1+n)-a-1;
	for(int i=1;i<=n;i++){
		b[i]=lower_bound(a+1,a+len+1,b[i])-a;
	}
	int tot=sqrt(n),ss=sqrt(n);
	for(int i=1;i<=tot;i++){
		LL[i]=(i-1)*tot+1;
		RR[i]=i*tot;
	}
	if(RR[tot]<n){
		tot++;
		LL[tot]=RR[tot-1]+1;
		RR[tot]=n;
	}
	for(int i=1;i<=tot;i++){
		for(int j=LL[i];j<=RR[i];j++){
			pos[j]=i;
		}
	}
	for(int i=1;i<=tot;i++){
		for(int j=LL[i];j<=RR[i];j++){
			cnt[i][b[j]]++;
		}
		for(int j=1;j<=len;j++){
			cnt[i][j]+=cnt[i-1][j];
		}
	}
	for(int i=1;i<=tot;i++){
		for(int j=i;j<=tot;j++){
			int mx=cnt2[i][j-1];
			for(int k=LL[j];k<=RR[j];k++){
				if(cnt[j][b[k]]-cnt[i-1][b[k]]>cnt[j][mx]-cnt[i-1][mx]||
				(cnt[j][b[k]]-cnt[i-1][b[k]]==cnt[j][mx]-cnt[i-1][mx]&&b[k]<mx)){
					mx=b[k];
					cnt2[i][j]=mx;
				}
			}
		}
	}
	int x=0;
	for(int i=1;i<=m;i++){
		int l0,r0;
		scanf("%d%d",&l0,&r0);
		int l=((l0+x-1)%n)+1,r=((r0+x-1)%n)+1;
		if(l>r) swap(l,r);
		x=query(l,r);
//		if(i==1){
//			for(int k=1;k<=tot;k++)
//				for(int j=1;j<=len;j++) cout<<k<<" "<<j<<" "<<cnt[k][j]<<endl;
//		}
		printf("%d\n",x);
	}
	return 0;
}