#include<bits/stdc++.h>
using namespace std;
int n,m,T,a[40010],ls[40010],p,k,w[1000][1000],ton[40010],l,r,L,R,ans,ll[500],rr[500];
vector<int> tp[40010];
inline void read(int &x){
	x=0; char ch; ch=getchar();
	int f=1;
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	x=f*x;
	return ;
}
inline void write(int x){
	if (x<0) cout<<'-';
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cin.tie(0);
	read(n);read(m);
	T=sqrt(n*log2(n));
	k=ceil(n*1.0/T);
	for (int i=1;i<=n;i++) read(a[i]),ls[i]=a[i];
	sort(ls+1,ls+n+1);
	int p=unique(ls+1,ls+n+1)-ls-1;
	for (int i=1;i<=n;i++){
		a[i]=lower_bound(ls+1,ls+p+1,a[i])-ls;
		tp[a[i]].push_back(i);
	}
	int pl=1,pr=1;
	for (int i=1;i<=k;++i){
		while (pl<(i-1)*T+1) --ton[a[pl++]];
		ll[i]=(i-1)*T+1;
		rr[i]=min(i*T,n); 
		if (i%2==1){
			for (int j=i;j<=k;++j){
				int o=0;
				while (pr<min(n,j*T)) ++ton[a[++pr]];
				for (int v=1;v<=p;++v) if (ton[v]>ton[o]) o=v;
				w[i][j]=o;
			}
		}
		else {
			for (int j=k;j>=i;--j){
				int o=0;
				while (pr>min(n,j*T)) --ton[a[pr--]];
				for (int v=1;v<=p;++v) if (ton[v]>ton[o]) o=v;
				w[i][j]=o;
			}
		}
	}
	while (m--){
		read(l); read(r);
		l=(l+ls[ans]-1)%n+1;
		r=(r+ls[ans]-1)%n+1;
		ans=0;int aans=0;
		if (l>r) swap(l,r);
		for (int i=1;i<=p;i++) ton[i]=0;
		L=1; R=k;
		while (ll[L]<l) ++L;
		while (rr[R]>r) --R;
		ton[w[L][R]]++;
		L=ll[L]; R=rr[R];
		for (int i=l;i<min(r,L);++i) ++ton[a[i]];
		for (int i=max(l,R+1);i<=r;++i) ++ton[a[i]];
		for (int i=1;i<=p;i++){
			if (ton[i]){
				int u=(upper_bound(tp[i].begin(),tp[i].end(),r)-tp[i].begin())-(lower_bound(tp[i].begin(),tp[i].end(),l)-tp[i].begin());
				if (u>aans){
					aans=u;
					ans=i;
				}
			}
		}
		write(ls[ans]);
		putchar('\n');
	}
	return 0;
}