#include<bits/stdc++.h>
using namespace std;
const int N = 4e4 + 9,SqrtN = 2e2 + 9;
int n,m,ans;
int a[N],tmp[N],len;
int block_cnt,block_len;
struct block{
	int start,end,size;
} b[SqrtN];
int belong[N];
int p[SqrtN][SqrtN];
int s[SqrtN][N];
void build(){
	block_cnt = (int)sqrt(n);
    for (int i = 1; i <= block_cnt; i++) {
        b[i].start = n / block_cnt * (i - 1) + 1;
        b[i].end = n / block_cnt * i;
    }
    b[block_cnt].end = n;
    for (int i = 1; i <= block_cnt; i++) {
        for (int j = b[i].start; j <= b[i].end; j++)
            belong[j] = i;
        b[i].size = b[i].end - b[i].start + 1;
    }
}
int cnt[N];
void init(){
	for(int i = 1;i <= block_cnt;i++){
		for(int j = 1;j <= len;j++)
			s[i][j] = s[i - 1][j];
		for(int j = b[i].start;j <= b[i].end;j++)
			s[i][a[j]]++;
	}
	for(int i = 1;i <= block_cnt;i++)
		for(int j = i;j <= block_cnt;j++){
			int Max = 0,Max_cnt = 0;
			memset(cnt,0,sizeof cnt);
			for(int k = b[i].start;k <= b[j].end;k++){
				cnt[a[k]]++;
				if(cnt[a[k]] > Max_cnt || (cnt[a[k]] == Max_cnt && a[k] < Max)){
					Max = a[k];
					Max_cnt = cnt[a[k]];
				}
			}
			p[i][j] = Max;
		}
}
int query(int l,int r){
	int pos_l = belong[l],pos_r = belong[r];
	int Max = 0,Max_cnt = 0;
	memset(cnt,0,sizeof cnt);
	if(pos_r - pos_l <= 1){
		for(int i = l;i <= r;i++){
			cnt[a[i]]++;
			if(cnt[a[i]] > Max_cnt || (cnt[a[i]] == Max_cnt && a[i] < Max)){
				Max = a[i];
				Max_cnt = cnt[a[i]];
			}
		}
		return Max;
	}
	int ret = p[pos_l + 1][pos_r - 1],ret_cnt = s[pos_r - 1][ret] - s[pos_l][ret];
	for(int i = l;i <= b[pos_l].end;i++){
		cnt[a[i]]++;
		if(cnt[a[i]] > Max_cnt || (cnt[a[i]] == Max_cnt && a[i] < Max)){
			Max = a[i];
			Max_cnt = cnt[a[i]];
		}
	}
	for(int i = b[pos_r].start;i <= r;i++){
		cnt[a[i]]++;
		if(cnt[a[i]] > Max_cnt || (cnt[a[i]] == Max_cnt && a[i] < Max)){
			Max = a[i];
			Max_cnt = cnt[a[i]];
		}
	}
	if(Max_cnt > ret_cnt || (Max_cnt == ret_cnt && Max < ret))
		ret = Max;
	return ret;
}
int main(){
//	freopen("P4168_1.in","r",stdin);
//	freopen("P4168.out","w",stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++){
		scanf("%d", &a[i]);
		tmp[i] = a[i];
	}
	sort(tmp + 1,tmp + n + 1);
	len = unique(tmp + 1,tmp + n + 1) - tmp - 1;
	for(int i = 1;i <= n;i++)
		a[i] = lower_bound(tmp + 1,tmp + len + 1,a[i]) - tmp;
	build();
	init();
	for(int i = 1;i <= m;i++){
		int l,r;
		scanf("%d%d", &l, &r);
		l = (l + ans - 1) % n + 1;
		r = (r + ans - 1) % n + 1;
		if(l > r)
			swap(l,r);
		ans = tmp[query(l,r)];
		printf("%d\n",ans);
	}
}