题目描述

$x\;nandy=not\;(xandy)$

$x$	$y$	$x\;nand\;y$
$0$	$0$	$1$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$0$

现在我们只考虑$k$位二进制数的$nand$操作。 给定一棵$n$个结点的树，每个结点有个点权w[i](0≤w[i]<2^k) 接下来有$m$个操作： ①.Replace\;x\;y (1≤x≤n，0≤y<2^k) 将结点 $x$ 的权值修改为 $y$，即 $w[x]=y$ ②.Query\;x\;y (1≤x<y≤n) 记从 $x$ 到 $y$ 的路径为$S_1,S_2,...,S_L$。 定义函数 $f(i) = \begin{cases}f(i-1)\;nand\;w[S_i]&(i>0)\\0\\ \end{cases}$ 询问发$f(L)$的值。

输入

第一行三个整数，$n,m,k$。 第二行$n$个整数，初始状态每个结点的权值。 接下来$n-1$行，每行两个整数$a.b$，表示$a$与$b$之间有一条边。 接下来$m$行，每行一个操作，格式见题目描述。

输出

对于每个$Query$操作输出一行，表示你的答案。

输入样例

3 3 3
2 7 3
1 2
2 3
Query 2 3
Replace 1 3
Query 1 1

输出样例

4
7

提示

【数据规模】 对于30%的数据，$1≤n,m≤1000$。 对于另外10%的数据，$k=1$。 对于另外20%的数据，$k=2$。 对于100%的数据，$1≤n,m≤10^5，1≤k≤32$。

查询端点说明

公开样例含Query 1 1，因此同点查询也是合法情况，按路径包含该点一次计算；原操作说明x<y的限制没有覆盖该样例。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。