该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

染染船长，返航！

修完船后，染染船长在规划返航路线，现在有一张地图摆在他的面前。

经过观察，染染发现地图上的路线呈现为一棵基环树的结构，也就是一张 $n$ 个点 $n$ 条边的简单（无重边无自环）连通无向图的形式。在基环树上的每个点代表一个贸易点，可以通过交易获得利润，点 $i$ 收获的利润为 $a_i$。

染染会选择一条从起点到终点的简单路径（不能重复经过点或边）用于返航，并且在返航过程中，染染会选择其中的连续一段进行交易，获得的总利润即这一段的利润和。形式化的，假设染染选择的路径依次经过点 $x_1, x_2, \cdots, x_k$，之后染染会选择连续的一段 $x_l, x_{l+1}, \cdots, x_r$，最终的总利润即 $a_{x_l} + a_{x_{l+1}} + \cdots + a_{x_r}$。染染当然希望最大化总利润，甚至交易利润为负时，染染也可以选择不进行交易。

然而，地图是模糊的，染染不能确定起点和终点，所以染染会多次询问如果起点和终点分别为 $s, t$ 时可以获得的最大利润。

除此之外，由于各个贸易点有自己的情况，所以某个贸易点 $x$ 的利润 $a_x$ 随时可能修改。

输入

本题单个测试点内包含多组测试数据。

• 输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。
• 每组数据第一行两个正整数 $n, q$ ($1 \leq n, q \leq 10^5, n \geq 3$)，分别表示基环树的点数和操作数量。
• 第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($-10^9 \leq a_i \leq 10^9$)，表示每个贸易点的利润。
• 接下来 $n$ 行，每行两个正整数 $x, y$ ($1 \leq x, y \leq n$) 表示基环树上的一条边。保证所有边构成基环树结构。
• 接下来 $q$ 行，每行开头一个英文大写字母 $Q$ 或 $C$。
  • 如果开头为 $Q$，则表示一个询问，接下来跟两个正整数 $s, t$ ($1 \leq s, t \leq n$)，表示询问从起点 $s$ 到终点 $t$ 可以获得的最大总利润。
  • 如果开头为 $C$，则表示一个修改，接下来跟两个整数 $x, v$ ($1 \leq x \leq n, -10^9 \leq v \leq 10^9$)，表示修改贸易点 $x$ 的利润 $a_x$ 为 $v$。

保证单个测试点内每组数据中 $n$ 的和与 $q$ 的和均不超过 $10^6$。

输出

为了避免输出量过大，输出对每组数据进行压缩。

对于每组数据，假设总共有 $k$ 次询问，第 $i$ 次询问的答案为 $r_i$，你只需要输出一行一个压缩后的非负整数 $R$：

其中 $\oplus$ 为按位异或运算，压缩结果即所有询问答案的异或和。

样例

1
10 5
1 2 -3 4 5 -1 -3 2 4 -7
2 4
3 5
4 3
2 5
1 3
1 6
1 7
8 5
2 9
4 10
Q 1 7
Q 6 9
C 5 -3
Q 6 9
Q 4 5

6

提示

• 第一次询问可以选择贸易点 $1$，利润为 $1 = 1$。
• 第二次询问可以选择贸易点 $5, 2, 9$，利润为 $5 + 2 + 4 = 11$。
• 第三次修改贸易点 $5$ 的利润为 $-3$。
• 第四次询问可以选择贸易点 $4, 2, 9$，利润为 $4 + 2 + 4 = 10$。
• 第五次询问可以选择贸易点 $4, 2$，利润为 $4 + 2 = 6$。