#3282. Tree

内存限制:512 MiB 时间限制:30 Sec

题目描述

给定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行,每行三个整数,分别代表操作类型和操作所需的量。
1<=N,M<=300000

输出格式

对于每一个0号操作,你须输出X到Y的路径上点权的Xor和。

样例

样例输入


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

样例输出


			
3
1

数据范围与提示