#include<bits/stdc++.h>
using namespace std;
int n,m,a[40005],b[40005],tot,x,t,len,pos[45],l[45],r[45],c[45][45][40005],d[45][45][2],now[2],l0,r0,l1,r1,tt,book[40005];
int ask(int l1,int r1){
	int p=pos[l1],q=pos[r1];
	if(p+1<=q-1){
		now[0]=d[p+1][q-1][0];
		now[1]=d[p+1][q-1][1];
		for(int i=l1;i<=r[p];i++){
			c[p+1][q-1][a[i]]++;
			if(c[p+1][q-1][a[i]]>now[0]||c[p+1][q-1][a[i]]==now[0]&&a[i]<now[1]){
				now[0]=c[p+1][q-1][a[i]];
				now[1]=a[i];
			}
		}
		for(int i=l[q];i<=r1;i++){
			c[p+1][q-1][a[i]]++;
			if(c[p+1][q-1][a[i]]>now[0]||c[p+1][q-1][a[i]]==now[0]&&a[i]<now[1]){
				now[0]=c[p+1][q-1][a[i]];
				now[1]=a[i];
			}
		}
		for(int i=l1;i<=r[p];i++){
			c[p+1][q-1][a[i]]--;
		}
		for(int i=l[q];i<=r1;i++){
			c[p+1][q-1][a[i]]--;
		}
		return now[1];
	}
	else{
		memset(book,0,sizeof(book));
		now[1]=0;now[0]=0;
		for(int i=l1;i<=r1;i++){
			book[a[i]]++;
			if(book[a[i]]>now[0]||book[a[i]]==now[0]&&a[i]<now[1]){
				now[0]=book[a[i]];
				now[1]=a[i];
			}
		}
		return now[1];
	}
}
bool cmp(int x,int y) {
	return x<y;
}
int main(){
	freopen("1972.in","r",stdin);
	freopen("1972.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		b[i]=a[i];
	}
	sort(b+1,b+1+n,cmp);
	tot=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
	}
	t=(int)pow((double) n,(double) 1/3);
	len=t*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++) {
			pos[j]=i;
		}
	}
	for(int i=1;i<=t;i++){
		for(int j=i;j<=t;j++){
			for(int k=l[i];k<=r[j];k++){
				c[i][j][a[k]]++;
				if(c[i][j][a[k]]>d[i][j][0]||c[i][j][a[k]]==d[i][j][0]&&a[i]<d[i][j][1]){
					d[i][j][0]=c[i][j][a[k]];
					d[i][j][1]=a[i];
				}
			}
		}
	}
	for(int i=1;i<=m;i++){
		cin>>l0>>r0;
		l1=((l0+x-1)%n)+1;
		r1=((r0+x-1)%n)+1;
		if (l1>r1) swap(l1,r1); 
		if (l1<1) l1=1;
		if (r1>n) r1=n; 
		x=ask(l1,r1);
		x=b[x];
		cout<<x<<endl;
	} 
	return 0;
}