友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
$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$。