MnZn 分块求条！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10;
const int B = 220;
int n, m, nm, blk, tot, lst;
array<int, N> a;
int b[N];
array<int, N> bl;
array<int, B> cl, cr;
array<array<int, B>, B> p;
array<array<int, B>, N> s; 
array<int, N> t;

void Read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];    
}

void Lisan()
{
    for (int i = 1; i <= n; i++)
        b[i] = a[i];
    sort(b + 1, b + n + 1);
    nm = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + nm + 1, a[i]) - b;    
}

void Init_Block()
{
    blk = round(sqrt(n)); tot = n / blk;
    if (n % blk) tot++;
    for (int i = 1; i <= n; i++)
        bl[i] = (i - 1) / blk + 1;
    for (int i = 1; i <= tot; i++)
        cl[i] = cr[i - 1] + 1, cr[i] = i * blk;
    cr[tot] = blk;
}

void Init_Ans()
{
    for (int i = 1; i <= tot; i++)
    {
        for (int j = 1; j <= n; j++)
            s[i][a[j]] = s[i - 1][a[j]];
        for (int j = cl[i]; j <= cr[i]; j++)
            s[i][a[j]]++;
    }
    for (int i = 1; i <= tot; i++)
    {
        t.fill(0); 
        for (int j = i; j <= tot; j++)
        {
            int ans = p[i][j - 1];
            for (int k = cl[j]; k <= cr[j]; k++)
            {
                t[a[k]]++;
                if (t[a[k]] > t[ans])
                    ans = a[k];
                if (t[a[k]] == t[ans])
                    ans = min(ans, a[k]);
            }
            p[i][j] = ans;
        }
    }
}

int Query(int l, int r)
{
    t.fill(0);
    if (bl[r] - bl[l] <= 2)
    {
        int ans = 0;
        for (int i = l; i <= r; i++)
        {
            t[a[i]]++;
            if (t[a[i]] > t[ans])
                ans = a[i];
            if (t[a[i]] == t[ans])
                ans = min(ans, a[i]);           
        }
        return ans;
    }
    else
    {
        int ql = bl[l], qr = bl[r];
        for (int i = l; i <= cr[ql]; i++)
            if (!t[a[i]]) t[a[i]] += s[qr - 1][a[i]] - s[ql][a[i]];
        for (int i = cl[qr]; i <= r; i++)
            if (!t[a[i]]) t[a[i]] += s[qr - 1][a[i]] - s[ql][a[i]];     

        int ans = 0;
        for (int i = l; i <= cr[ql]; i++)
        {
            if (t[a[i]] > t[ans]) ans = a[i];
            if (t[a[i]] == t[ans]) ans = min(ans, a[i]);            
        }   
        for (int i = cl[qr]; i <= r; i++)
        {
            if (t[a[i]] > t[ans]) ans = a[i];
            if (t[a[i]] == t[ans]) ans = min(ans, a[i]);            
        }

        int k = p[ql + 1][qr - 1];
        int res = s[qr - 1][k] - s[ql][k];
        for (int i = l; i <= cr[ql]; i++)
            if (a[i] == k) res++;
        for (int i = cl[qr]; i <= r; i++)
            if (a[i] == k) res++;

        if (res > t[ans] || (res == t[ans] && k < ans))
            ans = k;
        t.fill(0);
        return k;   
    }
}

void Solve()
{
    while (m--)
    {
        int l, r; cin >> l >> r;
        l = (l + lst - 1) % n + 1;
        r = (r + lst - 1) % n + 1;
        if (l > r)
            swap(l, r);
        lst = b[Query(l, r)];
        cout << lst << "\n";
    } 
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    Read();
    Lisan();
    Init_Block();
    Init_Ans();
    Solve();
    return 0;
}