#include<bits/stdc++.h>
using namespace std;
const int N=4e4+44;
int n,m,a[N],b[N],num,sum[220][N],f[220][220],bow[N];
int l0,r0,x;
int t,s,L[220],R[220],pos[N];
void disper(){
	for(int i=1;i<=n;i++)
		b[i]=a[i];
	sort(b+1,b+n+1);
	num=unique(b+1,b+n+1)-b-1;
//	printf("%d\n",num);
//	for(int i=1;i<=num;i++)
//		printf("%d ",b[i]);
//	printf("\n");
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+num+1,a[i])-b;
//	for(int i=1;i<=n;i++)
//		printf("%d ",a[i]);
//	printf("\n");
}
int query(int l,int r){
	int p=pos[l],q=pos[r],maj=0,now,pre;
	if(q-p<=1){
		for(int i=l;i<=r;i++)
			++bow[a[i]];
		for(int i=l;i<=r;i++)
			if(bow[a[i]]>bow[maj]||bow[a[i]]==bow[maj]&&a[i]<maj)
				maj=a[i];
		for(int i=l;i<=r;i++)
			bow[a[i]]=0;
		return maj;
	}
	maj=f[p+1][q-1];
	for(int i=l;i<=R[p];i++)
		++bow[a[i]];
	for(int i=L[q];i<=r;i++)
		++bow[a[i]];
	for(int i=l;i<=R[p];i++){
		pre=bow[maj]+sum[q-1][maj]-sum[p][maj];
		now=bow[a[i]]+sum[q-1][a[i]]-sum[p][a[i]];
		if(now>pre||now==pre&&a[i]<maj)
			maj=a[i];
	}
	for(int i=L[q];i<=r;i++){
		pre=bow[maj]+sum[q-1][maj]-sum[p][maj];
		now=bow[a[i]]+sum[q-1][a[i]]-sum[p][a[i]];
		if(now>pre||now==pre&&a[i]<maj)
			maj=a[i];
	}
	for(int i=l;i<=R[p];i++)
		bow[a[i]]=0;
	for(int i=L[q];i<=r;i++)
		bow[a[i]]=0;
	return maj;
}
int main(){
//	freopen("P4168_1.in","r",stdin);
	scanf("%d%d",&n,&m);
	t=sqrt(n),s=n/t;
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	disper();
	for(int i=1;i<=t;i++)
		L[i]=(i-1)*s+1,R[i]=i*s;
	if(R[t]<n)
		L[++t]=R[t-1]+1,R[t]=n;
//	for(int i=1;i<=t;i++)
//		printf("%d %d %d\n",i,L[i],R[i]);
	for(int i=1;i<=t;i++){
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i,sum[i][a[j]]++;
		for(int j=1;j<=num;j++)
			sum[i][j]+=sum[i-1][j];
	}
//	for(int i=1;i<=n;i++)
//		printf("%d %d\n",a[i],pos[i]);
//	for(int i=1;i<=t;i++)
//		for(int j=1;j<=num;j++)
//			printf("#%d %d %d\n",i,j,sum[i][j]);
	for(int i=1;i<=t;i++)
		for(int j=i;j<=t;j++){
			int Maj=f[i][j-1];
			for(int k=L[j];k<=R[j];k++)
				if(sum[j][a[k]]-sum[i-1][a[k]]>sum[j][Maj]-sum[i-1][Maj]||a[k]<Maj&&sum[j][a[k]]-sum[i-1][a[k]]==sum[j][Maj]-sum[i-1][Maj])
					Maj=a[k];
			f[i][j]=Maj;
		}
//	for(int i=1;i<=t;i++)
//		for(int j=i;j<=t;j++)
//			printf("%d %d %d\n",i,j,f[i][j]);
	while(m--){
		scanf("%d%d",&l0,&r0);
		l0=((l0+x-1)%n)+1,r0=((r0+x-1)%n)+1;
		if(l0>r0)
			swap(l0,r0);
		printf("%d\n",x=b[query(l0,r0)]);
	}
	return 0;
}