LinkCutTree

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <limits>
#include <numeric>
#include <iostream>

#ifdef LBT_DEBUG
#define LOG(FMT...) fprintf(stderr, "[LOG MESSAGE]: " FMT)
#define OUT(X) std::cerr << "[LOG #" #X "]: " << X << std::endl
#else
#define LOG(FMT...)
#define OUT(X)
#endif

struct LinkCutTree {
    struct Node {
        int v, sum;
        bool rev;
        union {
            struct {
                Node *ls, *rs;
            };
            Node* ch[2];
        };
        Node *prt, *path;

        bool relation() const {
            return this == prt->rs;
        }

        void pushDown() {
            if (rev) {
                std::swap(ls, rs);
                if (ls)
                    ls->rev = !ls->rev;
                if (rs)
                    rs->rev = !rs->rev;
                rev = false;
            }
        }

        void update() {
            sum = v;
            if (ls)
                sum ^= ls->sum;
            if (rs)
                sum ^= rs->sum;
        }

        void rotate() {
            if (prt->prt)
                prt->prt->pushDown();
            prt->pushDown();
            pushDown();
            path = prt->path;
            prt->path = NULL;
            bool rel = relation();
            Node* p = prt;
            if (p->prt)
                p->prt->ch[p->relation()] = this;
            prt = p->prt;
            p->ch[rel] = ch[!rel];
            if (ch[!rel])
                ch[!rel]->prt = p;
            ch[!rel] = p;
            p->prt = this;
            p->update();
            update();
        }

        void splay() {
            while (prt) {
                if (prt->prt == NULL) {
                    rotate();
                    return;
                }
                prt->prt->pushDown();
                prt->pushDown();
                if (relation() == prt->relation()) {
                    prt->rotate();
                    rotate();
                } else {
                    rotate();
                    rotate();
                }
            }
        }

        void expose() {
            splay();
            pushDown();
            if (rs) {
                rs->prt = NULL;
                rs->path = this;
                rs = NULL;
                update();
            }
        }

        bool splice() {
            splay();
            if (!path)
                return false;
            path->expose();
            path->rs = this;
            prt = path;
            path = NULL;
            prt->update();
            return true;
        }

        void access() {
            expose();
            while (splice());
        }

        void evert() {
            access();
            splay();
            rev = !rev;
        }

        int query() {
            access();
            splay();
            return sum;
        }
    };

    static const int N = 300010;

    Node vertex[N];

    bool linked(int u, int v) {
        vertex[u].evert();
        vertex[v].access();
        vertex[v].splay();
        vertex[v].pushDown();
        return vertex[v].ls == vertex + u;
    }

    void link(int u, int v) {
        vertex[v].evert();
        vertex[v].path = vertex + u;
    }

    void cut(int u, int v) {
        vertex[u].evert();
        vertex[v].access();
        vertex[v].splay();
        vertex[v].pushDown();
        vertex[v].ls->prt = NULL;
        vertex[v].ls = NULL;
        vertex[v].update();
    }

    int query(int u, int v) {
        vertex[u].evert();
        return vertex[v].query();
    }

    void update(int u, int x) {
        vertex[u].splay();
        vertex[u].v = x;
        vertex[u].update();
    }
};

typedef long long ll;

LinkCutTree linkCutTree;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        linkCutTree.update(i, x);
    }
    while (m--) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        switch (opt) {
            case 0:
                printf("%d\n", linkCutTree.query(x, y));
                break;
            case 1:
                if (!linkCutTree.linked(x, y))
                    linkCutTree.link(x, y);
                break;
            case 2:
                if (linkCutTree.linked(x, y))
                    linkCutTree.cut(x, y);
                break;
            case 3:
                linkCutTree.update(x, y);
                break;
            default:break;
        }
    }
    return 0;
}