题目描述

给定 $n$ 个点以及每个点的权值，要你处理接下来的 $m$ 个操作。操作有 $4$ 种。操作从 $0$ 到 $3$ 编号。点从 $1$ 到 $n$ 编号。

1. $0$：后接两个整数 $x$，$y$，代表询问从 $x$ 到 $y$ 的路径上的点的权值的异或和。保证 $x$ 到 $y$ 是联通的。
2. $1$：后接两个整数 $x$，$y$，代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。
3. $2$：后接两个整数 $x$，$y$，代表删除边 $(x,~y)$，不保证边 $(x,~y)$ 存在。
4. $3$：后接两个整数 $x$，$y$，代表将点 $x$ 上的权值变成 $y$。

输入格式

第 $1$ 行两个整数，分别为 $n$ 和 $m$，代表点数和操作数。
第 $2$ 行到第 $n + 1$ 行，每行一个整数，整数在 $1 \sim 10^9$ 内，代表每个点的权值。
第 $n + 2$ 行到第 $n + m + 1$ 行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式

对于每一个 $0$ 号操作，你须输出 $x$ 到 $y$ 的路径上点权的异或和。

3 3 
1
2
3
1 1 2
0 1 2 
0 1 1

3
1

提示

$1 \le n,m \le 3 \times 10^5$

题目来源

动态树