断断续续调了5天，没搞定。。。打表的部分应该没错。第一个调出来的我请饮料一杯任选！

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
// 分块代码的循环太多了，建议搞个宏
#define _for(a, b) for(int i=a; i<=b; i++)
#define _for_j(a, b) for(int j=a; j<=b; j++)

const int N = 4e4 + 10, SQRT_N = 2e2 + 10;
int L[SQRT_N], R[SQRT_N], pos[N];
int n, nblock; // 元素个数，分块的块数
int a[N], t[N]; // 原数组，离散化中间结果数组
int b[N]; // 离散化后的结果（排名）

// 离散化
void disc() {
	sort(t + 1, t + 1 + n);
	int num = unique(t + 1, t + 1 + n) - (t + 1);
	_for(1, n)
	b[i] = lower_bound(t + 1, t + 1 + num, a[i]) - t;
}

// 初始化分块相关的量
void init() {
	int t = sqrt(n); // 块的大小
	nblock = n / t; // 块数
	if (n % t) nblock++;
	// 求出每一块的左右端点
	_for(1, nblock) {
		L[i] = (i - 1) * t + 1;
		R[i] = i * t;
	}
	// 防止 n%t!=0 时出现错误
	R[nblock] = n;

	// 求出原数组每个元素分在哪一块
	_for(1, nblock) _for_j(L[i], R[i]) pos[j] = i;
}

// 第i块到第j块内的最小众数的编号！编号！编号！
int mx[SQRT_N][SQRT_N];
// 从第1块到第i块，（离散化后的）数字j出现的次数
int cnt[SQRT_N][N];
// 预处理分块统计的中间结果
void pre() {
	_for(1, nblock) {
		// 要把cnt[i]行的每一个数都复制到下一行
		_for_j(1, n) cnt[i][b[j]] = cnt[i - 1][b[j]];
		// 然后才是统计出现的数字
		_for_j(L[i], R[i]) cnt[i][b[j]]++;
		// 以上两个过程反过来也可以的，当然要注意用+=
	}

	// 统计第i~j块的众数
	_for(1, nblock) _for_j(i, nblock) {
		// val初始化为1表示块i的第一个数出现1次
		int idx = L[i], val = 1;
		// 从第i块的左端点到第j块的右端点
		for (int j2 = L[i]; j2 <= R[j]; j2++) {
			int e = 0;
			// mx[i][i]（每一块）的众数要单独处理
			if (i == j) e = cnt[j][b[j2]] - cnt[j - 1][b[j2]];
			// b[j2]在第i~j块内出现的次数
			else e = cnt[j][b[j2]] - cnt[j - i - 1][b[j2]];
			if (e > val || (e == val && b[j2] < b[idx])) {
				val = e;
				idx = j2;
			}
		}
		mx[i][j] = idx;
	}
}

void debug() {
	cout << "\n\nb:\n";
	_for(1, 16) cout << b[i] << ' ';

	cout << "\ncnt:\n";
	_for(1, 4) {
		_for_j(1, 16) cout << cnt[i][j] << ' ';
		cout << '\n';
	}
	cout << "a[mx[i][j]]:\n";
	_for(1, 4) {
		_for_j(1, 4) cout << a[mx[i][j]] << ' ';
		cout << '\n';
	}
	cout << '\n';
}

// 暂存统计结果
int tmp[N];
// 返回值：众数的索引
int query(int x, int y) {
	// 先清空本次查询要用到的桶
	_for(x, y) tmp[b[i]] = 0;

	int p = pos[x], q = pos[y];
	if (q - p <= 1) {
		_for(x, y) tmp[b[i]]++;
		int key = x;
		_for(x, y)
		if ((tmp[b[i]] == tmp[b[key]] && b[i] < b[key])
		    || tmp[b[i]] > tmp[b[key]])
			key = i;
		return key;
	}

	// 左端
	_for(x, R[p]) tmp[b[i]]++;
	// 右端
	_for(L[q], y) tmp[b[i]]++;
	// 对于头、尾两段里出现的每一个数，求出次数最多的那个数
	int key = x, maxval = 0;
	_for(x, R[p]) {
		int tot = tmp[b[i]] + cnt[q - 1][b[i]] - cnt[p][b[i]];
		if ((tot == maxval && b[i] < b[key])
		    || tot > maxval)
			key = i, maxval = tot;
	}
	_for(L[q], y) {
		int tot = tmp[b[i]] + cnt[q - 1][b[i]] - cnt[p][b[i]];
		if ((tot == maxval && b[i] < b[key])
		    || tot > maxval)
			key = i, maxval = tot;
	}
	// 再与 [x,y] 的区间众数（加头尾出现次数）进行比较
	// 众数（离散化后）
	int bmax = b[mx[p + 1][q - 1]];
	// 众数在 [x,y] 内出现的次数
	int tot = tmp[bmax] + cnt[q - 1][bmax] - cnt[p][bmax];
	if ((maxval == tot && bmax < b[key]) || maxval < tot)
		key = mx[p + 1][q - 1];
	return key;
}

int main() {
	freopen("P4168_1.in", "r", stdin);
	//freopen("test.in", "w", stdout);
	int m;
	cin >> n >> m;
	_for(1, n) cin >> a[i], t[i] = a[i];
	disc();
	init();
	pre();
//	debug();

	int x = 0;
	while (m--) {
		int l0, r0, l1, r1, l2, r2;
		cin >> l0 >> r0;
		l1 = (l0 + x - 1) % n + 1;
		r1 = (r0 + x - 1) % n + 1;
		l2 = min(l1, r1), r2 = max(l1, r1);
		// 调试用
//		l2 = l0, r2 = r0;

		// 查询区间众数的索引
		x = query(l2, r2);
		cout << a[x] << '\n';
	}

	return 0;
}