#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_N = 4*1e4+5, MAX_B = 255;
ll l1, r1, g[MAX_B][MAX_N], anss, n, m, a[MAX_N], b[MAX_N], q[MAX_N], ls[MAX_B], rs[MAX_B], t[MAX_N], B;
struct h{
	ll num, ma;
}f[MAX_B][MAX_B];
void yuchuli(){
	for (int i = 1; i <= q[n]; i++){
		for (int j = ls[i];  j <= n; j++){
			g[i][a[j]]++;
//			cout << a[j] <<endl;
			if (g[i][a[j]]>f[i][q[j]].num){
				f[i][q[j]].num = g[i][a[j]];
				f[i][q[j]].ma = a[j];
			}
			else if (g[i][a[j]]==f[i][q[j]].num&&f[i][q[j]].ma>a[j]){
				f[i][q[j]].num = g[i][a[j]];
				f[i][q[j]].ma = a[j];
			}
		}
//		cout << 1e10 << endl;
	}
	return;
}
ll ask(ll l, ll r){
	if (l > r) swap(l,r); 
	h ans;
	ans.num = 0;
	ans.ma = 0;
	if (q[l]==q[r]){
		for (int i = l; i <= r; i++){
			t[a[i]]++;
			if (t[a[i]]>ans.num){
				ans.num = t[a[i]];
				ans.ma = a[i];
			}
			else if (t[a[i]]==ans.num&&ans.ma>a[i]){
				ans.ma = a[i];
			}
		}
		for (int i = l; i <= r; i++) t[a[i]] = 0;
		return ans.ma;
	}
	if (q[l]+1<=q[r]-1)
		ans = f[q[l]+1][q[r]-1];
	for (int i = l; i <= rs[q[l]]; i++){
		t[a[i]]++;
		ll ans1 = g[q[l]+1][a[i]]-g[q[r]][a[i]];
		if (t[a[i]]+ans1>ans.num){
			ans.num = t[a[i]]+ans1;
			ans.ma = a[i];
		}
		else if (t[a[i]]+ans1==ans.num&&ans.ma>a[i]){
			ans.ma = a[i];
		}
	}
	ll t1[MAX_N];
	for (int i = ls[q[r]]; i <= r; i++){
		t1[a[i]]++;
		ll ans1 = g[q[l]+1][a[i]]-g[q[r]][a[i]];
		if (t[a[i]]+t1[a[i]]+ans1>ans.num){
			ans.num = t[a[i]]+t1[a[i]]+ans1;
			ans.ma = a[i];
		}
		else if (t[a[i]]+ans1+t1[a[i]]==ans.num&&ans.ma>a[i]){
			ans.ma = a[i];
		}
	}
	for (int i = l; i <= rs[q[l]]; i++) t[a[i]] = t1[a[i]] = 0;
	for (int i = ls[q[r]]; i <= r;i++) t[a[i]] = t1[a[i]] = 0;
	return ans.ma;
}
int main(){
	cin >> n >> m;
	ll tot = 0;
	B = sqrt(n);
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		b[++tot] = a[i];
	}
	sort (b+1,b+tot+1);
	ll re = unique(b+1,b+tot+1)-b-1;
	for (int i = 1; i <= n; i++){
		a[i] = lower_bound(b+1,b+re+1,a[i])-b;
	}
	for (int i = 1; i <= n; i++){
		q[i] = (i-1)/B+1;
		if (q[i]!=q[i-1]){
			rs[q[i-1]] = i-1;
			ls[q[i]] = i;
		}
	}
	rs[q[n]] = n;
	yuchuli();
	while (m--){
		cin >> l1 >> r1;
		anss = b[ask((l1+anss-1)%n+1,(r1+anss-1)%n+1)];
		cout << anss << endl;
	}
	return 0;
}
//p[i]->i所对应的块, ls,rs->每个块的左右端点， t1,t->桶.
//g[i][j]后缀数组，从第i块到末尾i的出现次数。
//b数组->离散化数组，a数组->原数组，f[i][j].num->从i块到j块出现最多的数的次数
//f[i][j].ma->从第i块到第j块出现最多的数，ans同理