异或Tree

题号：NC205397
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

前置定义：（牛逼值）

给定一个长度为n的数组： $a_1,a_2,a_3...a_n$ ，该数组的牛逼值为： $(\sum_{i=1}^na_i)+\sum_{i=1}^n\sum_{j=i+1}^n(a_i \oplus a_{i+1}\oplus ...\oplus a_j)$ 。其中 $\oplus$ 表示异或运算，与传统异或运算定义一致。

例如长度为3的数组： $a_1=1,a_2=2,a_3=3$ ，那么他的牛逼值为：

$(a_1+a_2+a_3)+(a_1\oplus a_2)+(a_1\oplus a_2\oplus a_3)+(a_2\oplus a_3)$ =10。

题面：

lt是一个三维生物，他掌管着二维世界的运行规律，某一天他发现一颗有 $n$ 个节点的无根树，该树只有点权，没有边权，现在他要进行 $m$ 次操作，每次进行以下两种操作之一：

选择一个节点，将其点权进行修改。
给出参数u,v，询问u->v的简单路径上的所有点按顺序组成一个数组，计算这个数组的牛逼值。

输入描述:

单组输入。
第一行输入n,m，代表树的节点个数，以及进行的操作次数，保证。
第二行输入n个正整数，代表每个节点的点权，保证输入值。
接下来n-1行，每行两个正整数u,v，表示节点与节点之间有一条双向边，保证输入规模为一颗树，且1<=u,v<=n且u!=v。
接下来m行，每行三个数字id,u,v，保证1<=id<=2。
若id=1，则表示是第一种操作，此时，将节点u的点权修改为v。
若id=2，则表示是第二种操作1<=u,v<=n，此时，你需要输出该次询问结果。

输出描述:

对于每个第二种操作输出一行，表示该次询问的结果。
保证64位整数可以存下结果

示例1

输入

复制

输出

复制

22
50

说明


对于第一次询问，节点2->节点3的简单路径上所有点权按顺序组成的数组是{2,1,4}
牛逼值=2+1+4+(2^1)+(2^1^4)+(1^4)=22。

第二次操作，将节点1的点权修改为8。

第三次的询问操作，组成的数组为{2,8,4}
牛逼值=2+8+4+(2^8)+(2^8^4)+(8^4)=50

示例2

输入

复制

10 10
4 3 1 1 6 1 6 2 8 10 
1 2
2 3
2 4
4 5
5 6
3 7
3 8
2 9
9 10
1 4 1
2 10 5
1 2 9
1 9 10
2 5 4
2 1 1
2 1 9
1 8 8
2 2 6
2 6 2

输出

复制

说明

一组友好的帮助debug的大样例