与非

【题目描述】

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

现在我们只考虑$k$位二进制数的$nand$操作。 给定一棵$n$个结点的树，每个结点有个点权w[i](0≤w[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$。