#1529. Tree

Tree

Description

给定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。

Format

Input

第1行两个整数,分别为N和M,代表点数和操作数。

第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。

第N+2行到第N+M+1行,每行三个整数,分别代表操作类型和操作所需的量。

1<=N,M<=300000

Output

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

Samples

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