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

题目背景

动态树

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3
1

说明

数据范围: $ 1 \leq N \leq {10}^5,1 \leq m \leq 3 \times {10}^5$