#include<bits/stdc++.h>
using namespace std;
const int N=40005;
typedef long long ll;
ll a[N],b[N];
int L[N],R[N],t;
int pos[N];
int cnt[40][40][N],zs[40][40],zsc[40][40],mxm,mxn,p,q,lf,ri,f[N];
void check(int j) {
//	cout<<lf<<" "<<ri<<" "<<j<<": ";
	cnt[lf][ri][a[j]]++;
//		cout<<cnt[lf][ri][a[j]]<<endl;
	if (cnt[lf][ri][a[j]]>mxn || (cnt[lf][ri][a[j]]==mxn && a[j]<mxm)) {
		mxn=cnt[lf][ri][a[j]];
		mxm=a[j];
	}
}
int main() {
	int n,m;
	scanf("%d %d",&n,&m);
	t=(int)pow(n*1.0,1.0/3.0);
//	cout<<t<<endl;
	int T;
	if(t) T=n/t;
	for (int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		//cout<<i<<":"<<a[i];
		//puts("");
		b[i]=a[i];
	}
	//return 0;
	sort(b+1,b+1+n);
	int cnti=unique(b+1,b+1+n)-b;
	for (int i=1; i<=n; i++) {
		a[i]=lower_bound(b+1,b+1+cnti,a[i])-b;
	}
	for (int i=1; i<=cnti; i++) f[a[i]]=b[i];
	for (int i=1; i<=t; i++) {
		L[i]=(i-1)*T+1;
		R[i]=i*T;
	}
	if (R[t]<n) {
		t++;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for (int i=1; i<=t; i++) {
		for (int k=i; k<=t; k++) {
			for (int j=L[i]; j<=R[k]; j++) {
				cnt[i][k][a[j]]++;
			}
			for (int j=1; j<=cnti; j++) {
				if (cnt[i][k][j]>zsc[i][k] || cnt[i][k][j]==zsc[i][k] && j<zs[i][j]) {
					zs[i][k]=j;
					zsc[i][k]=cnt[i][k][j];
				}
			}
		}
	}
	int x=0;
	for (int i=1; i<=m; i++) {
		ll l0,r0;
		ll l,r;
		scanf("%lld %lld",&l0,&r0);
		l=(l0+x-1)%n+1;
		r=(r0+x-1)%n+1;
		if (l>r) swap(l,r);
		for (int j=1; j<=t; j++) if (l<=R[j]) {
				p=j;
				break;
			}
		for (int j=t; j>=1; j--) if (r>=L[j])	{
				q=j;
				break;
			}
		if (p+1<=q-1) {
			lf=l+1;
			ri=r-1;
		} else {
			lf=ri=0;
		}
		mxn=zsc[lf][ri],mxm=zs[lf][ri];
		if (p==q) {
			for (int j=l; j<=r; j++) check(j);
			for (int j=l; j<=r; j++) cnt[lf][ri][a[j]]--;
		} else {
			for (int j=l; j<=R[p]; j++) check(j);
			for (int j=L[q]; j<=r; j++) check(j);
			for (int j=l; j<=R[p]; j++) cnt[lf][ri][a[j]]--;
			for (int j=L[q]; j<=r; j++) cnt[lf][ri][a[j]]--;
		}
		printf("%d\n",f[mxm]);
		x=f[mxm];
	}
	return 0;
}