RT

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a[100001], b[100001], tag[100001]; // a: 原数组 b: 离散化后的数组
ll n, m, sum, len;
ll f[500][500], s[500][50010];
ll buk[100001]; // 临时桶
// f(i, j): i ~ j 块中的众数
// s(i, j): j 在前 i 块中出现的次数

ll solve(ll l, ll r)
{
	ll ans = 0, lt = tag[l], rt = tag[r];
	if (tag[l] == tag[r])
	{
		for (int i = l; i <= r; i++) buk[b[i]]++;
		for (int i = l; i <= r; i++)
			if ((buk[b[i]] > buk[ans]) || (buk[b[i]] == buk[ans] && b[i] < ans)) ans = b[i];
		for (int i = l; i <= r; i++) buk[b[i]] = 0;
		return a[ans];
	}
	else
	{
		ans = f[lt + 1][rt - 1];
		for (int i = l; i <= min(n, lt * len); i++)
			buk[b[i]]++;
		for (int i = (rt - 1) * len + 1; i <= r; i++)
			buk[b[i]]++;
		
		for (int i = l; i <= min(n, lt * len); i++)
		{
			int now = buk[b[i]] + s[rt - 1][b[i]] - s[lt][b[i]],
			org = buk[ans] + s[rt - 1][ans] - s[lt][ans];
			if ((now > org) || ((now == org) && b[i] < ans))
				ans = b[i];
		}
		for (int i = (rt - 1) * len + 1; i <= r; i++)
		{
			int now = buk[b[i]] + s[rt - 1][b[i]] - s[lt][b[i]],
			org = buk[ans] + s[rt - 1][ans] - s[lt][ans];
			if ((now > org) || ((now == org) && b[i] < ans))
				ans = b[i];
		}
		
		for (int i = l; i <= min(n, lt * len); i++)
			buk[b[i]] = 0;
		for (int i = (rt - 1) * len + 1; i <= r; i++)
			buk[b[i]] = 0;
		return a[ans];
	}
}

int main()
{
	cin >> n >> m;
	len = int(sqrt(n));
	for (int i = 1; i <= n; i++)
		cin >> a[i], b[i] = a[i], tag[i] = (i - 1) / len + 1;
	sort(a + 1, a + n + 1);
	sum = unique(a + 1, a + n + 1) - a - 1;
	for (int i = 1; i <= n; i++)
		b[i] = lower_bound(a + 1, a + 1 + sum, b[i]) - a;
	for (int i = 1; i <= tag[n]; i++)
	{
		for (int j = (i - 1) * len + 1; j <= min(n, len * i); j++)
			s[i][b[j]]++;
		for (int j = 1; j <= sum; j++)
			s[i][j] += s[i - 1][j];
	}
	
	for (int i = 1; i <= tag[n]; i++)
		for (int j = i; j <= tag[n]; j++)
		{
			int maxx = f[i][j - 1];
			for (int k = (j - 1) * len + 1; k <= min(len * j, n); k++)
				if ( (s[j][b[k]] - s[i - 1][b[k]] > s[j][maxx] - s[i - 1][maxx])
					|| ( (s[j][b[k]] - s[i - 1][b[k]] == s[j][maxx] - s[i - 1][maxx]) && b[k] < maxx) )
					maxx = b[k];
			f[i][j] = maxx;
		}
	
	ll l, r, x = 0;
	while (m--)
	{
		ll l0, r0;
		cin >> l0 >> r0;
		l = ((l0 + x - 1) % n) + 1, r = ((r0 + x - 1) % n) + 1;
		if (l > r) swap(l, r);
		x = solve(l, r);
		cout << x << endl;
	}
	return 0;
}