题目背景

“像糟糕的作业一样糟糕。”

题目描述

$ben$同学最讨厌做作业了。

现在，老师布置给了$ben$同学$n$份作业，每份作业有一个难度值$A_i$。

一开始，每份作业都是独立的。有一些操作，每次在两份作业$x,y$间加一条边或删除一条边。

由于老师喜怒无常，因此还有一些操作，是将两份作业$x,y$之间路径上的所有作业的难度值都$xor$上一个值。

同时，为了满足$ben$同学的好奇心，你需要回答两份作业$x,y$之间的所有作业的难度$and$和、难度$or$和、难度$xor$和以及难度和。

输入格式

第一行两个正整数$n,q$，分别表示作业份数和操作个数。

接下来一行，$n$个自然数$A_1,...,A_n$，表示每份作业的难度值。

接下来$q$行，每行一个操作：

• $L\ x\ y$：在$x,y$两份作业之间连一条边。（保证不会形成环，即任何时候这张图都是一个森林）
• $C\ x\ y$：删除$x,y$两份作业之间的边。（保证这条边存在且不会被删除多次）
• $U\ x\ y\ v$：将$x,y$两份作业之间路径上的所有作业的难度值都$xor$上$v$。（包括这两份作业，且保证联通，下同）
• $A\ x\ y$：询问$x,y$两份作业之间的所有作业的难度$and$和。
• $O\ x\ y$：询问$x,y$两份作业之间的所有作业的难度$or$和。
• $X\ x\ y$：询问$x,y$两份作业之间的所有作业的难度$xor$和。
• $S\ x\ y$：询问$x,y$两份作业之间的所有作业的难度和。

输出格式

对于每一个$A,O,X,S$操作，输出答案。

4 10
1 2 3 4
L 1 2
L 2 3
L 2 4
A 1 4
U 3 4 2
O 1 4
C 2 4
L 3 4
X 1 4
S 1 3

0
7
6
2

提示

对于$10\%$的数据，$n=100,m=100$。

另有$10\%$的数据，$n=5000,m=5000$。

另有$20\%$的数据，$n=10000,m=10000$。

对于$100\%$的数据，$2\le n,m\le100000,0\le A_i<2^{30}$。