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

const int N = 4e4 + 5;
const int Sq_N = 2e2 + 5;

int n, m, lenth, num, x, n_range;
int a[N], b[N], c[N], pos[N], d[N];
int L[N], R[N];
int s[Sq_N][N];	// s[i][j] means the times number j appears in the first ith parts 
int p[Sq_N][Sq_N], buc[N];	// p[i][j] means the majority from the ith to the jth parts, buc means bucket

void discrete() {
	for (int i = 1; i <= n; i++) b[i] = a[i];
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++)
		if (i == 1 || b[i] != b[i - 1]) d[++n_range] = b[i];
}

int query(int x) {
	return lower_bound(d + 1, d + n_range + 1, x) - d;
}

void prework() {
	// discrete
	discrete();
	for (int i = 1; i <= n; i++) c[i] = query(a[i]);
	// apart
	lenth = sqrt(n), num = (n - 1) / lenth + 1;
	x = 0;
	for (int i = 1; i <= num; i++) L[i] = (i - 1) * lenth + 1, R[i] = min(n, L[i] + lenth - 1);
	for (int i = 1; i <= num; i++)
		for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
	// pre1
	for (int i = 1; i <= n; i++)
		for (int j = pos[i]; j <= num; j++) s[j][c[i]]++;
	// pre2
	for (int i = 1; i <= num; i++) {
		memset(buc, 0, sizeof(buc));
		for (int j = i; j <= num; j++) {
			p[i][j] = p[i - 1][j];
			for (int k = L[j]; k <= R[j]; k++) {
				buc[c[k]]++;
				if (buc[c[k]] > buc[p[i][j]] || (buc[c[k]] == buc[p[i][j]] && c[k] < p[i][j]))
					p[i][j] = c[k];
			}
		}
	}
	// Reset
	memset(buc, 0, sizeof(buc));
}

// Good job, Ahsoka. >o< 
int ahsoka(int l, int r) {
	int ans = 0;
	if (pos[r] - pos[l] <= 2) {
		for (int i = l; i <= r; i++) {
			buc[c[i]]++;
			if (buc[c[i]] > buc[ans] || (buc[c[i]] == buc[ans] && c[i] < ans))
				ans = c[i];
		}
		for (int i = l; i <= r; i++) buc[c[i]] = 0;
		return ans;
	}
	// different parts
	// Middle part
	for (int i = l; i <= R[pos[l]]; i++)
		if (!buc[c[i]]) buc[c[i]] += s[pos[r] - 1][c[i]] - s[pos[l]][c[i]];
	for (int i = L[pos[r]]; i <= r; i++)
		if (!buc[c[i]]) buc[c[i]] += s[pos[r] - 1][c[i]] - s[pos[l]][c[i]];
	// Rest par brute
	for (int i = l; i <= R[pos[l]]; i++) {
		buc[c[i]]++;
		if (buc[c[i]] > buc[ans] || (buc[c[i]] == buc[ans] && c[i] < ans))
			ans = c[i];
	}
	for (int i = L[pos[r]]; i <= r; i++) {
		buc[c[i]]++;
		if (buc[c[i]] > buc[ans] || (buc[c[i]] == buc[ans] && c[i] < ans))
			ans = c[i];
	}
	// The majority in the middle parts
	int k = p[pos[l] + 1][pos[r] - 1];
	int cnt = s[pos[r] - 1][k] - s[pos[l]][k];	// see it as buc[k]!!!
	for (int i = l; i <= R[pos[l]]; i++)
		if (c[i] == k) cnt++;
	for (int i = L[pos[r]]; i <= r; i++)
		if (c[i] == k) cnt++;
	if (cnt > buc[ans] || (cnt == buc[ans] && k < ans)) ans = k;
	// Reset
	for (int i = l; i <= R[pos[l]]; i++) buc[c[i]] = 0;
	for (int i = L[pos[r]]; i <= r; i++) buc[c[i]] = 0;
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	prework();
	for (int i = 1; i <= m; i++) {
		int l0, r0, l, r;
		scanf("%d%d", &l0, &r0);
		l = (l0 + x - 1) % n + 1, r = (r0 + x - 1) % n + 1;
		if (l > r) swap(l, r);
		x = d[ahsoka(l, r)];
		printf("%d\n", x);
	}
	return 0;
}