FHQ TREAP WA 92pts求调qwq

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd((unsigned)time(NULL));

struct node;
typedef node* nodeptr;
nodeptr root;
struct node
{
    nodeptr ch[2];
    int val, siz; unsigned pri;

    node(int x): ch{}, val{x}, siz{1}, pri{rnd()}
    {}

    void PushUp()
    {
        siz = 1;
        if (ch[0]) siz += ch[0]->siz;
        if (ch[1]) siz += ch[1]->siz;
    }
};

nodeptr Merge(nodeptr x, nodeptr y)
{
    if (!x || !y)
        return x ? x : y ? y : nullptr;
    if (x->pri < y->pri)
    {
        x->ch[1] = Merge(x->ch[1], y);
        x->PushUp(); return x;
    }
    else
    {
        y->ch[0] = Merge(x, y->ch[0]);
        y->PushUp(); return y;
    }
}

void Split(nodeptr now, int k, nodeptr &x, nodeptr &y)
{
    if (!now) 
        x = y = nullptr;
    else
    {
        if (now->val <= k)
        {
            x = now; Split(now->ch[1], k, x->ch[1], y);
        }
        else
        {
            y = now; Split(now->ch[0], k, x, y->ch[0]);
        } 
        now->PushUp();       
    }
}

void Insert(int val)
{
    nodeptr x, y, now = new node(val);
    Split(root, val - 1, x, y);
    root = Merge(Merge(x, now), y);
}

void Delete(int val)
{
    nodeptr x, y, z;
    Split(root, val, x, z);
    Split(x, val - 1, x, y);
    if (y) y = Merge(y->ch[0], y->ch[1]);
    root = Merge(Merge(x, y), z);
}

int Rank(int val)
{
    nodeptr x, y; int ans;
    Split(root, val - 1, x, y);
    ans = x ? x->siz : 0;
    root = Merge(x, y);
    return ans;
}

int Kth(nodeptr now, int k)
{
    if (!now) return 0;
    int siz = now->ch[0] ? now->ch[0]->siz : 0;
    if (k <= siz) return Kth(now->ch[0], k);
    if (k == siz + 1) return now->val;
    return Kth(now->ch[1], k - siz - 1);
}

int Pre(int val)
{
    nodeptr x, y; int ans;
    Split(root, val - 1, x, y);
    ans = Kth(x, x->siz);
    root = Merge(x, y);
    return ans;
}

int Nxt(int val)
{
    nodeptr x, y; int ans;
    Split(root, val, x, y);
    ans = Kth(y, 1);
    root = Merge(x, y);
    return ans;
}

void work()
{
    int n, m, last = 0, ans = 0;
    cin >> n >> m;
    root = nullptr;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        Insert(x);
    }
    while (m--)
    {
        int op, x, num = 0; 
        cin >> op >> x;
        x ^= last;
        if (op == 1) Insert(x);
        if (op == 2) Delete(x);
        if (op == 3) num = Rank(x) + 1;
        if (op == 4) num = Kth(root, x);
        if (op == 5) num = Pre(x); 
        if (op == 6) num = Nxt(x);
        ans ^= num; 
        if (num) last = num;
    }
    cout << ans << "\n";
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1, opinput = 0;
    if (opinput) cin >> T;
    while (T--) work();
    return 0;
}