code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int MAXN=40005;
const int MAXM=2005;

template <class T>
void read(T &x){
	x=0;bool f=false;char c=getchar();
	while(c<'0'||'9'<c) f=c=='-',c=getchar();
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
	x=f? (-x):x;
}

int n,m,a[MAXN],lsh[MAXN],len,block,tmp[MAXN];

int L[MAXM],R[MAXM],belong[MAXN],cnt[MAXM][MAXN],f[MAXM][MAXM];
bool vis[MAXN];

int sum(int l,int r,int x){
	if (l>r) return 0;
	return cnt[r][x]-cnt[l-1][x];
}

int query(int l,int r){
	int q=belong[l],p=belong[r],ans=0;	
	if (q==p){
		for (int i=l;i<=r;i++){
			++tmp[a[i]];
			if ((tmp[a[i]]>tmp[ans])||(tmp[a[i]]==tmp[ans]&&a[i]<ans)) ans=a[i];
		}
		for (int i=l;i<=r;i++) tmp[a[i]]--;
		return lsh[ans];
	}
	ans=f[q+1][p-1];int ret=ans;
	tmp[ans]=sum(q+1,p-1,ans);
	vis[ans]=true;
	for (int i=l;i<=R[q];i++){
		tmp[a[i]]++;
		if (!vis[a[i]]){
			tmp[a[i]]+=sum(q+1,p-1,a[i]);
			vis[a[i]]=true;
		}
	}
	for (int i=L[p];i<=r;i++){
		tmp[a[i]]++;
		if (!vis[a[i]]){
			tmp[a[i]]+=sum(q+1,p-1,a[i]);
			vis[a[i]]=true;
		}
	}
	for (int i=l;i<=R[q];i++){
		if ((tmp[a[i]]>tmp[ans])||((tmp[a[i]]==tmp[ans])&&a[i]<ans)) ans=a[i];
	}
	for (int i=L[p];i<=r;i++){
		if ((tmp[a[i]]>tmp[ans])||((tmp[a[i]]==tmp[ans])&&a[i]<ans)) ans=a[i];
	}
	for (int i=l;i<=R[q];i++) tmp[a[i]]=0,vis[a[i]]=0;
	for (int i=L[p];i<=r;i++) tmp[a[i]]=0,vis[a[i]]=0;
	tmp[ret]=0;vis[ret]=0;
	return lsh[ans];
}

int l0,r0,last,x,y;

int main(){
	read(n);read(m);
	for (int i=1;i<=n;i++) read(a[i]),lsh[i]=a[i];	
	sort(lsh+1,lsh+1+n);
	int tot=unique(lsh+1,lsh+1+n)-lsh-1;
	for (int i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+1+tot,a[i])-lsh;
	}
	len=sqrt(n);block=n/len;
	if (len*block!=n) block++;
	for (int i=1;i<=block;i++){
		L[i]=R[i-1]+1;
		R[i]=min(i*len,n);
		for (int j=L[i];j<=R[i];j++){
			belong[j]=i;
		}
	}

	for (int i=1;i<=block;i++){
		for (int j=1;j<=n;j++) cnt[i][j]=cnt[i-1][j];
		for (int j=L[i];j<=R[i];j++)	cnt[i][a[j]]++;
	}
	for (int i=1;i<=block;i++){
		memset(tmp,0,sizeof(tmp));
		for (int j=i;j<=block;j++){
			for (int k=L[j];k<=R[j];k++){
				tmp[a[k]]++;
				if ((tmp[a[k]]>tmp[f[i][j]])||((tmp[a[k]]==tmp[f[i][j]])&&a[k]<f[i][j])) f[i][j]=a[k];
			}
		}
	}
	memset(tmp,0,sizeof(tmp));
	while(m--){
		read(l0);read(r0);
		x=((l0+last-1)%n)+1,y=((r0+last-1)%n)+1;
		if (x>y) swap(x,y);
		printf("%lld\n",last=query(x,y));
	}
}