#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10;
const int B = 220;
int n, m, nm, blk, tot, lst;
array<int, N> a;
int b[N];
array<int, N> bl;
array<int, B> cl, cr;
array<array<int, B>, B> p;
array<array<int, B>, N> s; 
array<int, N> t;


void Read()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];	
}

void Lisan()
{
	for (int i = 1; i <= n; i++)
		b[i] = a[i];
	sort(b + 1, b + n + 1);
	nm = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(b + 1, b + nm + 1, a[i]) - b;	
}

void Init_Block()
{
	blk = round(sqrt(n)); tot = n / blk;
	if (n % blk) tot++;
	for (int i = 1; i <= n; i++)
		bl[i] = (i - 1) / blk + 1;
	for (int i = 1; i <= tot; i++)
		cl[i] = cr[i - 1] + 1, cr[i] = i * blk;
	cr[tot] = blk;
}

void Init_Ans()
{
	for (int i = 1; i <= tot; i++)
	{
		for (int j = 1; j <= n; j++)
			s[i][a[j]] = s[i - 1][a[j]];
		for (int j = cl[i]; j <= cr[i]; j++)
			s[i][a[j]]++;
	}
	for (int i = 1; i <= tot; i++)
	{
		t.fill(0); 
		for (int j = i; j <= tot; j++)
		{
			int ans = p[i][j - 1];
			for (int k = cl[j]; k <= cr[j]; k++)
			{
				t[a[k]]++;
				if (t[a[k]] > t[ans])
					ans = a[k];
				if (t[a[k]] == t[ans])
					ans = min(ans, a[k]);
			}
			p[i][j] = ans;
		}
	}
}

int Query(int l, int r)
{
	t.fill(0);
	if (bl[r] - bl[l] <= 2)
	{
		int ans = 0;
		for (int i = l; i <= r; i++)
		{
			t[a[i]]++;
			if (t[a[i]] > t[ans])
				ans = a[i];
			if (t[a[i]] == t[ans])
				ans = min(ans, a[i]);			
		}
		return ans;
	}
	else
	{
		int ql = bl[l], qr = bl[r];
		for (int i = l; i <= cr[ql]; i++)
			if (!t[a[i]]) t[a[i]] += s[qr - 1][a[i]] - s[ql][a[i]];
		for (int i = cl[qr]; i <= r; i++)
			if (!t[a[i]]) t[a[i]] += s[qr - 1][a[i]] - s[ql][a[i]];		
			
		int ans = 0;
		for (int i = l; i <= cr[ql]; i++)
		{
			if (t[a[i]] > t[ans]) ans = a[i];
			if (t[a[i]] == t[ans]) ans = min(ans, a[i]);			
		}	
		for (int i = cl[qr]; i <= r; i++)
		{
			if (t[a[i]] > t[ans]) ans = a[i];
			if (t[a[i]] == t[ans]) ans = min(ans, a[i]);			
		}
		
		int k = p[ql + 1][qr - 1];
		int res = s[qr - 1][k] - s[ql][k];
		for (int i = l; i <= cr[ql]; i++)
			if (a[i] == k) res++;
		for (int i = cl[qr]; i <= r; i++)
			if (a[i] == k) res++;
		
		if (res > t[ans] || (res == t[ans] && k < ans))
			ans = k;
		t.fill(0);
		return k;	
	}
}

void Solve()
{
	while (m--)
	{
		int l, r; cin >> l >> r;
		l = (l + lst - 1) % n + 1;
		r = (r + lst - 1) % n + 1;
		if (l > r)
			swap(l, r);
		lst = b[Query(l, r)];
		cout << lst << "\n";
	} 
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Read();
	Lisan();
	Init_Block();
	Init_Ans();
	Solve();
	return 0;
}