#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <cstdio>
using namespace std;
const int N = 40040;
const int K = 220;
int s[K][N],lshou[N],pos[N],n,m,f[K][K],t[N],MAX = 0,ans = 0;
map<long long,int> mm;
long long lsqian[N],ls[N],a[N];
int main()
{
	cin >> n >> m;
	int sqrt1 = sqrt(n);
	for(int i = 1; i <= n; i++)
	{
		cin >> lsqian[i];
		ls[i] = lsqian[i];
	}
	sort(lsqian + 1,lsqian + n + 1);
	for(int i = 1; i <= n; i++)
	{
		if(lsqian[i - 1] == 0)
		{
			mm[lsqian[i]] = 1;
		}
		else if(lsqian[i - 1] == lsqian[i])
		{
			continue;
		}
		else
		{
			mm[lsqian[i]] = mm[lsqian[i - 1]] + 1;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		lshou[i] = mm[ls[i]];
		pos[i] = (i - 1) / sqrt1 + 1; 
	}
	for(int i = 1; i <= n; i++)
	{
		a[lshou[i]] = ls[i];
	}
	int sum=std::unique(lshou+1, lshou+1+n)-lshou-1;
	for(int i = 1; i <= pos[n]; i++)
	{
		for(int j = (i - 1) * sqrt1 + 1; j <= min(sqrt1 * i,n); j++)
		{
			s[i][lshou[j]]++;
		}
		for(int j = 1; j <= sum; j++)
		{
			s[i][j] += s[i - 1][j];
		}
	}
	for(int i = 1; i <= pos[n]; i++)
	{
		for(int j = i; j <= pos[n]; j++)
		{
			int MAX = f[i][j - 1];
			for(int k = (j - 1) * sqrt1 + 1; k <= min(n,j * sqrt1); k++)
			{
				if((s[j][lshou[k]] - s[i - 1][lshou[k]] > s[j][MAX] - s[i - 1][MAX] ) ||
				 ((s[j][lshou[k]] - s[i - 1][lshou[k]] == s[j][MAX] - s[i - 1][MAX]) &&
				  (lshou[k] < MAX)))
				{
					MAX = lshou[k];
				}
			}
			f[i][j] = MAX;
		}
	}
	while(m--)
	{
		int l0,r0,l,r;
		cin >> l0 >> r0;
		l = (l0 - 1 + ans) % n + 1;
		r = (r0 - 1 + ans) % n + 1;
		if(l > r) swap(l,r);
		int pl = pos[l],pr = pos[r];
		MAX = 0;
		if(pr - pl <= 1)
		{
			for(int j = l; j <= r; j++)
			{
				t[lshou[j]]++;
			}
			for(int j = l; j <= r; j++)
			{
				if((t[lshou[j]] > t[MAX]) || (t[lshou[j]] == t[MAX] && lshou[j] < MAX))
				{
					MAX = lshou[j];
				}
			}
			for(int j = l; j <= r; j++)
			{
				t[lshou[j]] = 0;
			}
		}
		else
		{
			for(int j = l; j <= pl * sqrt1; j++)
			{
				t[lshou[j]]++;
			}
			for(int j = (pr - 1) * sqrt1 + 1; j <= r; j++)
			{
				t[lshou[j]]++;
			}
			MAX = f[pl + 1][pr - 1];
			for(int j = l; j <= pl * sqrt1; j++)
			{
				int pre = t[MAX] + s[pr - 1][MAX] - s[pl][MAX];
				int now = t[lshou[j]] + s[pr - 1][lshou[j]] - s[pl][lshou[j]];
				if(now > pre || (now == pre && lshou[j] < MAX))
				{
					MAX = lshou[j];
				}
			}
			for(int j = (pr - 1) * sqrt1 + 1; j <= r; j++)
			{
				int pre = t[MAX] + s[pr - 1][MAX] - s[pl][MAX];
				int now = t[lshou[j]] + s[pr - 1][lshou[j]] - s[pl][lshou[j]];
				if(now > pre || (now == pre && lshou[j] < MAX))
				{
					MAX = lshou[j];
				}
			}
			for(int j = l; j <= pl * sqrt1; j++)
			{
				t[lshou[j]] = 0;
			}
			for(int j = (pr - 1) * sqrt1 + 1; j <= r; j++)
			{
				t[lshou[j]] = 0;
			}
		}
		ans = a[MAX];
		cout << ans << endl;
	}
	return 0;
}