#include <bits/stdc++.h>
using namespace std ;
const int N = 4e4 + 5 , NR = 2e2 + 5 ;
int n , m , a[N] , b[N] , c[N] , x , l0 , r0 , t , pos[N] , l[NR] , r[NR] , s[NR][N] , zh[NR][NR] , d[N] , sz ;
//a:原数组 b:排序数组 c:离散化数组 pos:对应块 s[i][j]:前i个块第j种的数量 zh[i][j]:第i到j块中最小众数的种类 d:临时桶
int query(int lt , int rt)
{
	int x = pos[lt] , y = pos[rt] , ans = 0 ;
	if(x == y)
	{
		for(int i = lt ; i <= rt ; i++)	d[c[i]]++ ;
		int maxn = d[c[lt]] , p = c[lt] ;
		for(int i = lt + 1 ; i <= rt ; i++)
		{
			if(d[c[i]] > maxn || (d[c[i]] == maxn && c[i] < p))
			{
				maxn = d[c[i]] ;
				p = c[i] ;
			}
		}
		ans = b[p] ;
		for(int i = lt ; i <= rt ; i++)	d[c[i]] = 0 ;
	}
	else
	{
		for(int i = lt ; i <= r[x] ; i++)	d[c[i]]++ ;
		for(int i = l[y] ; i <= rt ; i++)	d[c[i]]++ ;
		int tmp = zh[x + 1][y - 1] ;
		d[tmp] += s[y - 1][tmp] - s[x][tmp] ;
		int maxn = d[tmp] , p = tmp ;
		for(int i = lt ; i <= r[x] ; i++)
		{
			if(d[c[i]] > maxn || (d[c[i]] == maxn && c[i] < p))
			{
				maxn = d[c[i]] ;
				p = c[i] ;
			}
		}
		for(int i = l[y] ; i <= rt ; i++)
		{
			if(d[c[i]] > maxn || (d[c[i]] == maxn && c[i] < p))
			{
				maxn = d[c[i]] ;
				p = c[i] ;
			}
		}
		ans = b[p] ;
		for(int i = lt ; i <= r[x] ; i++)	d[c[i]] = 0 ;
		for(int i = l[y] ; i <= rt ; i++)	d[c[i]] = 0 ;
		d[tmp] = 0 ;
	}
	return ans ;
}
int main()
{
	cin >> n >> m ;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i] ;
		b[i] = a[i] ;
	}
	sort(b + 1 , b + n + 1) ;
	sz = unique(b + 1 , b + n + 1) - b ;
	for(int i = 1 ; i <= n ; i++)	c[i] = lower_bound(b + 1 , b + sz + 1 , a[i]) - b ;
	t = sqrt(n) ;
	for(int i = 1 ; i <= t ; i++)
	{
		l[i] = r[i - 1] + 1 ;
		r[i] = i * t ;
	}
	if(r[t] < n)
	{
		t++ ;
		l[t] = r[t - 1] + 1 ;
		r[t] = n ;
	}
	for(int i = 1 ; i <= t ; i++)
	{
		for(int j = 1 ; j <= sz ; j++)	s[i][j] = s[i - 1][j] ;
		for(int j = l[i] ; j <= r[i] ; j++)
		{
			pos[j] = i ;
			s[i][c[j]]++ ;
		}
	}
	for(int i = 1 ; i <= t ; i++)
	{
		int maxn = 0 , p = INT_MAX ;
		for(int k = i ; k <= t ; k++)
		{
			for(int j = l[k] ; j <= r[k] ; j++)
			{
				d[c[j]]++ ;
				if(d[c[j]] > maxn || (d[c[j]] == maxn && c[j] < p))
				{
					maxn = d[c[j]] ;
					p = c[j] ;
				}
			}
			zh[i][k] = p ;
		}
		memset(d , 0 , sizeof d) ;
	}
	while(m--)
	{
		cin >> l0 >> r0 ;
		l0 = (l0 + x - 1) % n + 1 , r0 = (r0 + x - 1) % n + 1 ;
		if(l0 > r0)	swap(l0 , r0) ;
		x = query(l0 , r0) ;
		cout << x << '\n' ;
	}
	return 0 ;
}