萌新刚学分块，求调

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

#define ll long long
const int maxn = 40010;
const int maxp = 220;

int n, m, last, tot, x, y, T, L[maxp], R[maxp], block[maxn];
int a[maxn], d[maxp][maxp], sum[maxp][maxn], cnt[maxn], val[maxn];
vector<int>v;

void init(){
	for(int i = 1; i <= block[n]; i++){
		for(int j = L[i]; j <= R[i]; j++) sum[i][a[j]]++;
		for(int j = 1; j <= tot; j++) sum[i][j] += sum[i-1][j];
	}
	for(int i = 1; i <= block[n]; i++)
		for(int j = i; j <= block[n]; j++){
			int res = d[i][j-1];
			for(int k = L[j] - 1; k <= R[j]; k++)
				if(sum[j][res] - sum[i-1][res] < sum[j][a[k]] - sum[i-1][a[k]] || 
					(sum[j][res] - sum[i-1][res] == sum[j][a[k]] - sum[i-1][a[k]] && a[k] < res)) res = a[k];
			d[i][j] = res;
		}
}

int query(int x, int y){
	int p = block[x], q = block[y];
	if(q - p <= 1){
		int res = 0;
		for(int i = x; i <= y; i++) cnt[a[i]] = 0;
		for(int i = x; i <= y; i++) cnt[a[i]]++;
		for(int i = x; i <= y; i++) if(cnt[res] < cnt[a[i]] || (cnt[res] == cnt[a[i]] && res > a[i])) res = a[i];
		return res;
	}
	for(int i = x; i <= R[p]; i++) cnt[a[i]] = 0;
	for(int i = L[q]; i <= y; i++) cnt[a[i]] = 0;
	for(int i = x; i <= R[p]; i++) cnt[a[i]]++;
	for(int i = L[q]; i <= y; i++) cnt[a[i]]++;
	int res = d[p+1][q-1];
	for(int i = x; i <= R[p]; i++){
		int pre = cnt[res] + sum[q-1][res] - sum[p][res], now = cnt[a[i]] + sum[q-1][a[i]] - sum[p][a[i]];
		if(now > pre || (now == pre && res > a[i])) res = a[i];
	}
	for(int i = L[q]; i <= y; i++){
		int pre = cnt[res] + sum[q-1][res] - sum[p][res], now = cnt[a[i]] + sum[q-1][a[i]] - sum[p][a[i]];
		if(now > pre || (now == pre && res > a[i])) res = a[i];
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m; T = sqrt(n);
	for(int i = 1; i <= n; i++) block[i] = (i - 1) / T + 1;
	for(int i = 1; i <= block[n]; i++) L[i] = (i - 1) * T + 1, R[i] = min(n, i * T);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end()); tot = v.size(); 
	for(int i = 1; i <= n; i++){
		int t = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; 
		val[t] = a[i], a[i] = t;
	}
	init();
	while(m--){
		cin >> x >> y;
		x = (x + last - 1) % n + 1;
		y = (y + last - 1) % n + 1;
		if(x > y) swap(x, y);
		last = val[query(x, y)];
		cout << last << endl;
	}
	return 0;
}