问题 J: 返航

染染船长，返航！

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

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

染染会选择一条从起点到终点的简单路径（不能重复经过点或边）用于返航，并且在返航过程中，染染会选择其中的连续一段进行交易，获得的总利润即这一段的利润和。形式化的，假设染染选择的路径依次经过点 x1,x2,⋯,xkx1,x2,⋯,xk，之后染染会选择连续的一段 xl,xl+1,⋯,xrxl,xl+1,⋯,xr，最终的总利润即 axl+axl+1+⋯+axraxl+axl+1+⋯+axr。染染当然希望最大化总利润，甚至交易利润为负时，染染也可以选择不进行交易。

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

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

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

输入第一行一个正整数 $T(1\le T\le 20)$，表示数据组数。

每组数据第一行两个正整数 n,q (1≤n,q≤105,n≥3)n,q (1≤n,q≤105,n≥3)，分别表示基环树的点数和操作数量。

第二行 $n$ 个整数 a1,a2,⋯,an (−109≤ai≤109)a1,a2,⋯,an (−109≤ai≤109)，表示每个贸易点的利润。

接下来 $n$ 行，每行两个正整数 $x,y(1\le x,y\le n)$ 表示基环树上的一条边。保证所有边构成基环树结构。

接下来 $q$ 行，每行开头一个英文大写字母 $\text{Q}$ 或 $\text{C}$。

如果开头为 $\text{Q}$，则表示一个询问，接下来跟两个正整数 $s,t(1\le s,t\le n)$，表示询问从起点 $s$ 到终点 $t$ 可以获得的最大总利润。

如果开头为 $\text{C}$，则表示一个修改，接下来跟两个整数 x,v (1≤x≤n,−109≤v≤109)x,v (1≤x≤n,−109≤v≤109)，表示修改贸易点 $x$ 的利润 axax 为 $v$。

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

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

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

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

第一次询问可以选择贸易点 $1$，利润为 $1=1$。

第二次询问可以选择贸易点 $5,2,9$，利润为 $5+2+4=11$。

第三次修改贸易点 $5$ 的利润为 $-3$。

第四次询问可以选择贸易点 $4,2,9$，利润为 $4+2+4=10$。

第五次询问可以选择贸易点 $4,2$，利润为 $4+2=6$。