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