【模板】Link Cut Tree (动态树)

题目背景

动态树

题目描述

给定 $n$ 个点以及每个点的权值,要你处理接下来的 $m$ 个操作。 操作有四种,操作从 $0$ 到 $3$ 编号。点从 $1$ 到 $n$ 编号。 - `0 x y` 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\text{xor}$ 和。保证 $x$ 到 $y$ 是联通的。 - `1 x y` 代表连接 $x$ 到 $y$,若 $x$ 到 $y$ 已经联通则无需连接。 - `2 x y` 代表删除边 $(x,y)$,不保证边 $(x,y)$ 存在。 - `3 x y` 代表将点 $x$ 上的权值变成 $y$。

输入输出格式

输入格式


第一行两个整数,分别为 $n$ 和 $m$,代表点数和操作数。 接下来 $n$ 行,每行一个整数,整数在 $[1,10^9]$ 内,代表每个点的权值。 然后有 $m$ 行,每行三个整数,分别代表操作类型和操作所需的量。

输出格式


对于每一个 $0$ 号操作,你须输出一行一个整数,表示 $x$ 到 $y$ 的路径上点权的 $\text{xor}$ 和。

输入输出样例

输入样例 #1

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

输出样例 #1

3
1

说明

【数据范围】 对于 $100\%$ 的数据, $ 1 \leq n \leq {10}^5,1 \leq m \leq 3 \times {10}^5$。