#include<bits/stdc++.h>
using namespace std;
const int N=40010;
const int M=210;
int n,cnt,a[N],A[N],b[N],id[N],cs[M][M],f[M][M],nt=0;
map<int,int>lsh;
int h[N];
set<int>st;
void init(int n){
	int k,i;
	k=sqrt(n);
	for(i=0;i<n;i++){
		if(i%k==0)id[i/k+1]=i+1;
		b[i+1]=i/k+1;
	}
	id[(n-1)/k+2]=n+1;
	cnt=(n-1)/k+1;
}
int main(){
	int q,i,j,k,op,x,y,ans;
	scanf("%d%d",&n,&q);
	init(n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	for(i=1;i<=n;i++)A[i]=a[i];
	sort(A+1,A+n+1);
	for(i=1;i<=n;i++){
		if(st.count(A[i]))continue;
		st.insert(A[i]);
		lsh[A[i]]=++nt;
		h[nt]=A[i];
	}
	for(i=1;i<=n;i++)a[i]=lsh[a[i]];
	for(i=1;i<=cnt;i++){
		for(j=1;j<=nt;j++)cs[i][j]=cs[i-1][j];
		for(j=id[i];j<id[i+1];j++)cs[i][a[j]]++;
	}
	for(i=1;i<=cnt;i++){
		int mx=1;
		priority_queue<int,vector<int>,greater<int> >pq;
		for(j=1;j<=nt;j++){
			if(cs[i][j]-cs[i-1][j]>mx){
				mx=cs[i][j]-cs[i-1][j];
				while(!pq.empty())pq.pop();
				pq.push(j);
			}else if(cs[i][j]-cs[i-1][j]==mx)pq.push(j);
		}
		f[i][i]=pq.top();
	}
	for(i=1;i<=cnt;i++)for(j=i+1;j<=cnt;j++){
		int mx=cs[j][f[i][j-1]]-cs[i-1][f[i][j-1]];
		priority_queue<int,vector<int>,greater<int> >pq;
		pq.push(f[i][j-1]);
		for(k=id[j];k<id[j+1];k++){
			if(cs[j][a[k]]-cs[i-1][a[k]]>mx){
				mx=cs[j][a[k]]-cs[i-1][a[k]];
				while(!pq.empty())pq.pop();
				pq.push(a[k]);
			}else if(cs[j][a[k]]-cs[i-1][a[k]]==mx)pq.push(a[k]);
		}
		f[i][j]=pq.top();
	}
	int la=0;
	while(q--){
		scanf("%d%d",&x,&y);
		x=(x+la-1)%n+1;
		y=(y+la-1)%n+1;
		if(x>y)swap(x,y);
		int mx=1,sc[N]={0};
		bool ok[N]={0};
		priority_queue<int,vector<int>,greater<int> >pq;
		if(b[y]-b[x]<=1){
			for(i=x;i<=y;i++)sc[a[i]]++;
			for(i=x;i<=y;i++){
				if(sc[a[i]]>mx){
					mx=sc[a[i]];
					while(!pq.empty())pq.pop();
					pq.push(a[i]);
				}else if(sc[a[i]]==mx)pq.push(a[i]);
			}
			la=h[pq.top()];
			printf("%d\n",la);
		}else{
			mx=cs[b[y]-1][f[b[x]+1][b[y]-1]]-cs[b[x]][f[b[x]+1][b[y]-1]];
			pq.push(f[b[x]+1][b[y]-1]);
			for(i=x;i<id[b[x]+1];i++)sc[a[i]]++;
			for(i=id[b[y]];i<=y;i++)sc[a[i]]++;
			for(i=x;i<id[b[x]+1];i++)if(!ok[a[i]])sc[a[i]]+=(cs[b[y]-1][a[i]]-cs[b[x]][a[i]]),ok[a[i]]=1;
			for(i=id[b[y]];i<=y;i++)if(!ok[a[i]])sc[a[i]]+=(cs[b[y]-1][a[i]]-cs[b[x]][a[i]]),ok[a[i]]=1;
			for(i=x;i<id[b[x]+1];i++){
				if(sc[a[i]]>mx){
					mx=sc[a[i]];
					while(!pq.empty())pq.pop();
					pq.push(a[i]);
				}else if(sc[a[i]]==mx)pq.push(a[i]);
			}
			for(i=id[b[y]];i<=y;i++){
				if(sc[a[i]]>mx){
					mx=sc[a[i]];
					while(!pq.empty())pq.pop();
					pq.push(a[i]);
				}else if(sc[a[i]]==mx)pq.push(a[i]);
			}
			la=h[pq.top()];
			printf("%d\n",la);
		}
	}
	return 0;
}

只能过两个点