record

#include<bits/stdc++.h>
#define N 40005
#define SN 205
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
	return x * f;
}
int n, m, a[N], b[N], f[SN][SN], cnt[SN][N];
int B, len, l[SN], r[SN], belong[N];
int main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read(), m = read();
	B = sqrt(n), len = (n + B - 1) / B;
	for(int i = 1; i <= n; i++){
		a[i] = b[i] = read();
		belong[i] = (i - 1) / B + 1;
	}
	for(int i = 1; i <= len; i++)
	  l[i] = (i - 1) * B + 1, r[i] = i * B;
	r[len] = n;
	sort(b + 1, b + n + 1);
	int n1 = unique(b + 1, b + n + 1) - (b + 1);
	for(int i = 1; i <= n; i++){
		int k = lower_bound(b + 1, b + n1 + 1, a[i]) - b;
		a[i] = k; cnt[belong[i]][a[i]]++;
	}
	for(int i = 1; i <= len; i++)
	  for(int j = 1; j <= n1; j++)
	    cnt[i][j] += cnt[i - 1][j];
	for(int i = 1; i <= len; i++){
		int Ans = 0, Max = 0;
		for(int j = l[i]; j <= n; j++){
			int d = cnt[belong[j]][a[j]] - cnt[i - 1][a[j]];
			if(d > Max) Max = d, Ans = a[j];
			else if(d == Max && a[j] < Ans) Ans = a[j];
			if(j % B == 0 || j == n){
				f[i][belong[j]] = Ans;
			}
		}
	}
	int ans = 0;
	while(m--){
		int L = ((read() + ans - 1) % n) + 1;
		int R = ((read() + ans - 1) % n) + 1;
		if(L > R) swap(L, R);
		int p = belong[L], q = belong[R], Max = 0;
		if(p == q){
			for(int i = L; i <= R; i++){
				int res = 0;
				for(int j = L; j <= R; j++)
				  if(a[j] == a[i]) res++;
				if(res > Max) Max = res, ans = a[i];
				else if(res == Max && a[i] < ans) ans = a[i];
			}
		} else {
			ans = f[p + 1][q - 1], Max = cnt[q - 1][ans] - cnt[p][ans];
			//printf("ans = %lld, Max = %lld\n", ans, Max);
			for(int i = L; i <= r[p]; i++) if(a[i] == ans) Max++;
			for(int i = l[q]; i <= R; i++) if(a[i] == ans) Max++;
			for(int i = L; i <= r[p]; i++){
				int res = 0;
				for(int j = L; j <= r[p]; j++) if(a[j] == a[i]) res++;
				for(int j = l[q]; j <= R; j++) if(a[j] == a[i]) res++;
				res += cnt[q - 1][a[i]] - cnt[p][a[i]];
				if(res > Max) Max = res, ans = a[i];
				else if(res == Max && a[i] < ans) ans = a[i];
				//printf("res = %d, ans = %d, Max = %d\n", res, ans, Max);
			}
			for(int i = l[q]; i <= R; i++){
				int res = 0;
				for(int j = L; j <= r[p]; j++) if(a[j] == a[i]) res++;
				for(int j = l[q]; j <= R; j++) if(a[j] == a[i]) res++;
				res += cnt[q - 1][a[i]] - cnt[p][a[i]];
				if(res > Max) Max = res, ans = a[i];
				else if(res == Max && a[i] < ans) ans = a[i];
				//printf("res = %d, ans = %d, Max = %d\n", res, ans, Max);
			}
		}
		//printf("%d: ", ans);
		ans = b[ans];
		printf("%d\n", ans);
		//printf("\n");
	}
	return 0;
}