题目背景

FangZeLi 喜欢异或，所以就有了这道题（然而这并不是他出这种题的理由）。

题目描述

注意，本题中一切 $\sum$ 均表示求异或和！

一棵 $n$ 个节点，$n-1$ 条边的有根树，初始时以 $1$ 节点为根。

这棵树上的每个节点 $i$ 都有其点权 $V_{i}$。

令函数 $\operatorname{Xor}(x)=\sum_{y\in \operatorname{Subtree}(x)}{V_{y}}$，其中 $\operatorname{Subtree}(x)$ 表示 $x$ 的子树。

现需支持以下五种操作：

1. 1 x，表示将 $x$ 换为根，且查询 $\sum_{i=1}^{n}{\operatorname{Xor}(i)}$。
2. 2 x y，表示令 $V_{x}=y$。
3. 3 x y ，表示查询 $\operatorname{LCA}(x,y)$。
4. 4 x y，表示查询 $x$ 到 $y$ 路径上的点的点权异或和。
5. 5 x，表示查询 $\operatorname{Xor}(x)$。

输入格式

第一行三个整数，$n,m,q$，分别表示节点数，$1$ 操作个数，其余操作个数。

接下来一行 $n$ 个整数，表示 $V_{1}\dots V_{n}$。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 和 $y$ 间有一条边。

接下来 $m+q$ 行，每行两到三个整数，第一个数为操作序号，接下来为相应的操作。

输出格式

若干行，表示 $1,3,4,5$ 操作的结果。

5 4 4
0 0 2 2 1
1 2
1 3
2 4
2 5
1 1
1 1
1 1
2 3 0
4 3 3
5 1
1 2
3 1 2

3
3
3
0
3
0
2

10 8 8
5 6 2 1 0 4 0 0 0 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
3 10 9
2 1 6
1 5
1 4
1 7
1 7
5 1
1 1
3 1 5
1 7
1 9
2 5 0
4 9 6
1 10
4 10 7
5 1

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

提示

对于所有数据，保证 $100\le n,m,q\le 10^6$，$0\le V_i\le 2^{31}-1$。详细数据范围如下表。