Description:


首先知道A nand B=not(A and B) (运算操作限制了数位位数为K)比如2 nand 3,K=3,则2 nand 3=not (2 and 3)=not 2=5。
给出一棵树,树上每个点都有点权,定义树上从a到b的费用为0与路径上的点的权值顺次nand的结果,例如:从2号点到5号点顺次经过2->3->5,权值分别为5、7、2,K=3,那么最终结果为0 nand 5 nand 7 nand 2=7 nand 7 nand 2=0 nand 2=7,现在这棵树需要支持以下操作。
① Replace a b:将点a(1≤a≤N)的权值改为b。
② Query a b:输出点a到点b的费用。
请众神给出一个程序支持这些操作。

Input:


第一行N,M,K,树的节点数量、总操作个数和运算位数。
接下来一行N个数字,依次表示节点i的权值。
接下来N-1行,每行两个数字a,b(1≤a,b≤N)表示a,b间有一条树边。
接下来M行,每行一个操作,为以上2类操作之一。

Output:


对于操作②每个输出一行,如题目所述。

Sample Input:


Sample Output:


题解:


这一道题调了很久,还要感谢LYQ的帮助~
nand是一个神奇的东西,因为它既不满足交换律也不满足结合律~~
所以我们要按照二进制位来处理这个东西。
用LCT来做这个东西是极好的,虽然树链剖分也能够做~~
设f[i][j]表示i节点Splay中这一颗子树维护的序列中每一个数二进制第j位连在一起末尾1的个数的奇偶性。
因为nand 0必定等于1,nand 1等于xor 1。所以末尾1的奇偶性可以决定该位最后的取值。
然后用g存反过来的序列对应的值,因为有reverse操作~~~
代码如下: