Chef needs to return some videotapes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int MAXN = 1e5 + 5, B = 450;
int N, Q, last, t, a, b, lo, hi;
int C[MAXN], L[MAXN];
vector<int> psum, prv;
vector<int> block_order;
vector<set<int>> indices;

void recalc(int bid) {
    lo = bid * B, hi = min(N, (bid + 1) * B);
    sort(block_order.begin() + lo, block_order.begin() + hi, [&](int x, int y) {
        return prv[x] < prv[y];
    });
    for (int i = lo; i < hi; i++) {
        psum[i] = L[block_order[i]];
        if (i > lo) psum[i] += psum[i - 1];
    }
}

void solve() {
    cin >> N >> Q;
    indices.assign(N + 1, set<int>());
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> C[i];
        // C[i]--;
        // indices[C[i]].insert(i);
    }
    prv.assign(N + 1, -1);
    last = 0;
    psum.assign(N, 0);
    block_order.resize(N);
    iota(block_order.begin(), block_order.end(), 0);
    for (int i = 0; i < N; ++i) {
        if (!indices[C[i]].empty()) prv[i] = *indices[C[i]].rbegin();
        indices[C[i]].insert(i);
    }
    // vector<int> seen(N, -1);
    // for (int i = 0; i < N; i++) {
    //     prv[i] = seen[C[i]];
    //     seen[C[i]] = i;
    // }
    // for (int i = 0; i < N; i++) {
    //     cout << i << " " << prv[i] << endl;
    // }
    for (int i = 0; i < N; i += B) {
        recalc(i / B);
    }
    for (int q = 0; q < Q; q++) {
        cin >> t >> a >> b;
        if (t == 1) {
            int l, r;
            l = a ^ last;
            r = b ^ last;
            l--; r--;
            int lb = l / B, rb = r / B;
            last = 0;
            for (int bid = lb + 1; bid < rb; bid++) {
                lo = bid * B, hi = min(N, (bid + 1) * B);
                int idx = lower_bound(block_order.begin() + lo, block_order.begin() + hi, l, [&](int x, int y) {
                    return prv[x] < y;
                }) - block_order.begin();
                if (idx > lo) last += psum[idx - 1];
            }
            for (int i = l; i < min(r + 1, (lb + 1) * B); i++) {
                if (prv[i] < l) last += L[i];
            }
            if (lb != rb) {
                for (int i = rb * B; i <= r; i++) {
                    if (prv[i] < l) last += L[i];
                }
            }
            cout << last << endl;
        } else if (t == 2) {
            int x, y;
            x = a ^ last;
            y = b ^ last;
            x--;
            L[x] = y;
            recalc(x / B);
        } else {
            int pos, val;
            pos = a ^ last;
            val = b ^ last;
            pos--;
            auto it = indices[C[pos]].find(pos);
            int x = N, y = N;
            if (next(it) != end(indices[C[pos]])) {
                x = *next(it);
                prv[x] = prv[pos];
            }
            indices[C[pos]].erase(pos);
            
            indices[val].insert(pos);
            C[pos] = val;
            auto it2 = indices[val].find(pos);
            if (next(it2) != end(indices[val])) {
                y = *next(it2);
                prv[y] = pos;
            }
            if (it2 == begin(indices[val])) prv[pos] = -1;
            else prv[pos] = *prev(it2);
            if (x > y) swap(x, y);
            recalc(pos/B);
            // if (x != N and pos/B < x/B) recalc(x/B);
            // if (y != N and x/B < y/B) recalc(y/B);
            if (x < N) recalc(x/B);
            if (y < N) recalc(y/B);
            // int i, y, j, k;
            // i = a ^ last;
            // y = b ^ last;
            // i--; 
            // // y--;
            // j = N; k = N;
            // auto it = indices[C[i]].upper_bound(i);
            // if (it != indices[C[i]].end()) k = *it;
            // it = indices[y].upper_bound(i);
            // if (it != indices[y].end()) j = *it;
            // if (k < N) {
            //     prv[k] = prv[i];
            // }
            // prv[i] = prv[j];
            // if (j < N) {
            //     prv[j] = i;
            // }
            // indices[C[i]].erase(i);
            // recalc(i / B);
            // if (j < N) recalc(j / B);
            // if (k < N) recalc(k / B);
            // C[i] = y;
            // indices[C[i]].insert(i);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}