#include<bits/stdc++.h>
#include<cmath>
#define ld long double
#define ll long long
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)
#define N 40010
#define M 210
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pb push_back
#define mk make_pair
#define pque priority_queue

using namespace std;
int a[N],b[N],id[N];
int n,m,cnt,B;
int cs[M][N];
struct node{
	int mx=0,mw=2e9;
}p[M][M];
int ps[N];

ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void prework(){
	For(i,1,id[n]){
		For(j,1,cnt) cs[i][j]=cs[i-1][j];
		For(j,(i-1)*B+1,min(n,i*B)) cs[i][a[j]]++;
	}
	For(i,1,id[n]){
		For(j,1,cnt) ps[j]=0; 
		node tmp;
		tmp.mx=0;
		tmp.mw=2e9;
		For(j,i,id[n]){
			For(k,(j-1)*B+1,min(n,j*B)){
				ps[a[k]]++;
				if(ps[a[k]]>tmp.mx){
					tmp.mx=ps[a[k]];
					tmp.mw=a[k];
				}else if(ps[a[k]]==tmp.mx && a[k]<tmp.mw) tmp.mw=a[k];
			}
			p[i][j].mx=tmp.mx;
			p[i][j].mw=tmp.mw;
		}
	}
}

int main()
{
	n=read(),m=read();
	B=sqrt(n);
	For(i,1,n) id[i]=(i-1)/B+1;
	cnt=n;
	For(i,1,n) a[i]=b[i]=read();
	cnt=unique(b+1,b+cnt+1)-b-1;
	sort(b+1,b+cnt+1);
	For(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	//For(i,1,n) cout<<a[i]<<' ';
	//cout<<endl;
	prework();
	int lstans=0;
	while(m--){
		int l=(read()+lstans-1)%n+1,r=(read()+lstans-1)%n+1;
		if(l>r) swap(l,r);
		if(id[r]-id[l]<=1){
			node tmp;
			tmp.mx=0;
			tmp.mw=2e9;
			For(i,l,r){
				ps[a[i]]++;
				if(ps[a[i]]>tmp.mx){
					tmp.mx=ps[a[i]];
					tmp.mw=a[i];
				}else if(ps[a[i]]==tmp.mx && a[i]<tmp.mw) tmp.mw=a[i];
			}
			For(i,l,r) ps[a[i]]--;
			printf("%d\n",b[tmp.mw]);
			lstans=b[tmp.mw];
		}else{
			node tmp;
			tmp.mx=p[id[l]+1][id[r]-1].mx;
			tmp.mw=p[id[l]+1][id[r]-1].mw;
			for(int i=l;id[i]==id[l];i++) ps[a[i]]++;
			for(int i=r;id[i]==id[r];i--) ps[a[i]]++;
			for(int i=l;id[i]==id[l];i++){
				if(ps[a[i]]+cs[id[r]-1][a[i]]-cs[id[l]][a[i]]>tmp.mx){
					tmp.mx=ps[a[i]]+cs[id[r]-1][a[i]]-cs[id[l]][a[i]];
					tmp.mw=a[i];
				}else if(ps[a[i]]+cs[id[r]-1][a[i]]-cs[id[l]][a[i]]==tmp.mx && a[i]<tmp.mw) tmp.mw=a[i];
			}
			for(int i=r;id[i]==id[r];i--){
				if(ps[a[i]]+cs[id[r]-1][a[i]]-cs[id[l]][a[i]]>tmp.mx){
					tmp.mx=ps[a[i]]+cs[id[r]-1][a[i]]-cs[id[l]][a[i]];
					tmp.mw=a[i];
				}else if(ps[a[i]]+cs[id[r]-1][a[i]]-cs[id[l]][a[i]]==tmp.mx && a[i]<tmp.mw) tmp.mw=a[i];
			}
			for(int i=l;id[i]==id[l];i++) ps[a[i]]--;
			for(int i=r;id[i]==id[r];i--) ps[a[i]]--;
			printf("%d\n",b[tmp.mw]);
			lstans=b[tmp.mw];
		}
	}
	return 0;
}