XORTREE

题号：NC200191
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一颗 ${n}$ 个结点 ${n-1}$ 条边的带权树，第 ${i}$ 个结点的权值为 $a_{i}$ 。

定义点 ${u}$ 到点 ${v}$ 的路径的长度为点 ${u}$ 到点 ${v}$ 的最短路径上的所有结点的权值的异或和。

单独一个点不算做路径。

现在要求你维护 ${q}$ 个操作：

${1}$ ${u}$ ${x}$ 将点 ${u}$ 的权值修改为 ${x}$

${2}$ ${u}$ ${v}$ 求点 ${u}$ 到点 ${v}$ 之间的所有子路径的长度的异或和

输入描述:

第一行两个整数
第二行n个整数表示
接下来n-1行每行两个整数表示之间有一条边
接下来q行每行三个整数表示一个查询,数据保证对于查询，满足。

输出描述:

对于每个查询输出一行一个整数表示答案

示例1

输入

复制

输出

复制

6
12

说明

让表示点到点最短路径上所有结点的权值的异或和，那么第一个查询的答案为：

其中,其它的类似。

备注:

1<=u,v<=n,q<=2e5
1<=a_i，x<=1e9
建议使用快读
int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}