Terrible Homework

题目背景

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

题目描述

$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$操作,输出答案。

输入输出样例

输入样例 #1

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

输出样例 #1

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}$。