#include <bits/stdc++.h>
using namespace std;
const int N=40000+5;
const int T=800+5;
int n,m,t,len;
int a[N],b[N];
int L[T],R[T],pos[N];
int qzh[T][N]={0},zs[T][T];
vector<int>v[N];
int sum[N]={0};
int getsum(int x,int l,int r){
	int l1=0,r1=v[x].size()-1;
	while(l1<=r1){
		int mid=(l1+r1)/2;
		if (v[x][mid]>r)r1=mid-1;
		else l1=mid+1;
	}
	int l2=0,r2=v[x].size()-1;
	while(l2<=r2){
		int mid=(l2+r2)/2;
		if (v[x][mid]>=l)r2=mid-1;
		else l2=mid+1;
	}
	return l1-l2+1;
}
int ask(int l,int r){
	int p=pos[l],q=pos[r];
	int mx=0,now=0;
	if (p==q){
		memset(sum,0,sizeof(sum));
		for (int i=l;i<=r;i++){
			sum[a[i]]++;
			if (sum[a[i]]>mx||(sum[a[i]]==mx&&a[i]<now)){
				mx=sum[a[i]];now=a[i];
			}
		}
		return now;
	}
	now=zs[p+1][q-1];mx=getsum(now,l,r);
	for (int i=l;i<L[p+1];i++){
		int num=getsum(a[i],l,r);
		if (num>mx||(num==mx&&a[i]<now)){
			mx=num;now=a[i];
		}
	}
	for (int i=R[q-1]+1;i<=r;i++){
		int num=getsum(a[i],l,r);
		if (num>mx||(num==mx&&a[i]<now)){
			mx=num;now=a[i];
		}
	}
	return now;
}
int main(){
    freopen ("Dandelion.in","r",stdin);
    freopen ("Dandelion.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int cnt=unique(b+1,b+n+1)-b-1;
	for (int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	t=sqrt((double)n*log(n)/log(2));
	len=n/t;
	for (int i=1;i<=t;i++){
		L[i]=(i-1)*len+1;
		R[i]=i*len;
	} 
	if (R[t]<n){
		t++;
		L[t]=R[t-1]+1;R[t]=n;
	}
	for (int i=1;i<=t;i++){
		for (int j=L[i];j<=R[i];j++){
			qzh[i][a[j]]++;pos[j]=i;
			v[a[j]].push_back(j);
		}
		for (int j=1;j<=cnt;j++)qzh[i][j]+=qzh[i-1][j];
	}
	for (int i=1;i<=t;i++){
		for (int j=i;j<=t;j++){
			int now=zs[i][j-1];
			for (int k=L[j];k<=R[j];k++){
				if (qzh[j][a[k]]-qzh[i-1][a[k]]>qzh[j][now]-qzh[i-1][now])now=a[k];
				if (qzh[j][a[k]]-qzh[i-1][a[k]]==qzh[j][now]-qzh[i-1][now]&&a[k]<now)now=a[k];
			}
			zs[i][j]=now;
		}
	}
	int x=0;
	for (int i=1;i<=m;i++){
		int l,r;scanf("%d%d",&l,&r);
		l=(l+x-1)%n+1;r=(r+x-1)%n+1;
		if (l>r)swap(l,r);
		x=b[ask(l,r)];
		printf("%d\n",x);
	}
	return 0;
}