rt

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 5e5 + 5, M = 5005, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
int a[N], ls[N];
int pos[N], st[M], ed[M], f[M][M];
vector<int> ys, cnt[N]; 
void sol(int p)
{
	int v = 0, mxcnt = -1;
	vector<int> c(n + 1, 0);
	for(int i = st[p];i <= n;i ++)
	{
		int t = a[i];
		c[t] ++;
		if(c[t] > mxcnt || (c[t] == mxcnt && t < v)) v = t, mxcnt = c[t];
		f[p][pos[i]] = v;
	}
}
int query(int l, int r)
{
	int v = 0, mxcnt = -1;
	if(pos[l] == pos[r])
	{
		for(int i = l;i <= r;i ++)
		{
			int t = a[i], c = upper_bound(cnt[t].begin(), cnt[t].end(), r) - lower_bound(cnt[t].begin(), cnt[t].end(), l);
			if(c > mxcnt || (c == mxcnt && t < v)) v = t, mxcnt = c;
		}
	}
	else
	{
		v = f[pos[l] + 1][pos[r] - 1], mxcnt = upper_bound(cnt[v].begin(), cnt[v].end(), r) - lower_bound(cnt[v].begin(), cnt[v].end(), l);
		for(int i = l;i <= ed[pos[l]];i ++)
		{
			int t = a[i], c = upper_bound(cnt[t].begin(), cnt[t].end(), r) - lower_bound(cnt[t].begin(), cnt[t].end(), l);
			if(c > mxcnt || (c == mxcnt && t < v)) v = t, mxcnt = c;
		}
		for(int i = st[pos[r]];i <= r;i ++)
		{
			int t = a[i], c = upper_bound(cnt[t].begin(), cnt[t].end(), r) - lower_bound(cnt[t].begin(), cnt[t].end(), l);
			if(c > mxcnt || (c == mxcnt && t < v)) v = t, mxcnt = c;
		}
	}
	return v;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++)
		cin >> a[i], ys.push_back(a[i]);
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());
	for(int i = 1;i <= n;i ++)
	{
		int t = a[i];
		a[i] = lower_bound(ys.begin(), ys.end(), a[i]) - ys.begin();
		cnt[a[i]].push_back(i);
	}
	int lg = log2(n);
	int num = sqrt(n), len = n / len + (n % num ? 1 : 0);
	for(int i = 1;i <= num;i ++) st[i] = ed[i - 1] + 1, ed[i] = st[i] + len - 1;
	ed[num] = n;
	for(int i = 1;i <= num;i ++)
		for(int j = st[i];j <= ed[i];j ++)
			pos[j] = i;
	for(int i = 1;i <= num;i ++) sol(i);
	int x = 0;
	while(m --)
	{
		int l, r;
		cin >> l >> r;
		l = (l + x - 1) % n + 1, r = (r + x - 1) % n + 1;
		if(l > r) swap(l, r);
		x = ys[query(l, r)];
		cout << x << '\n';
	}
    return 0;
}