2539. 动态树

给定 $n$ 个点,编号从 $1$ 到 $n$,其中第 $i$ 个点的初始权值为 $a_i$。

现在要对这些点进行 $m$ 次操作,操作共分为以下 $4$ 种:

  • 0 x y,表示询问点 $x$ 到点 $y$ 之间的路径上的所有点(包括两端点)的权值的异或和。保证 $x$ 和 $y$ 之间存在连通路径。
  • 1 x y,表示在点 $x$ 和点 $y$ 之间增加一条边 $(x,y)$。注意:如果两点已经处于连通状态,则无视该操作
  • 2 x y,表示删除边 $(x,y)$。注意:如果该边不存在,则无视该操作
  • 3 x w,表示将点 $x$ 的权值修改为 $w$。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数,表示 $n$ 个点的初始权值。

接下来 $m$ 行,每行包含一个操作,格式如题目所述。

输出格式

对于每个查询操作 0 x y,输出一个占一行的整数表示答案。

数据范围

$1 \le n \le 10^5$,
$1 \le m \le 3 \times 10^5$,
$1 \le x,y \le n$,
$x \neq y$,
$1 \le a_i,w \le 10^9$

输入样例:

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

输出样例:

0
2