题目描述

在一片土地上有 $N$ 个城市，通过 $N-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $value[i]$。

不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。

接下来你需要在线处理 $M$ 次操作：

• 0 x k 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
• 1 x y 表示第 $x$ 个城市的价值变成了 $y$。

为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$。

输入格式

第一行包含两个正整数 $N$ 和 $M$。 第二行包含 $N$ 个正整数，第 $i$ 个数表示 $value[i]$。 接下来 $N-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。 接下来 $M$ 行，每行包含三个数，表示 $M$ 次操作。

输出格式

包含若干行，对于每个询问输出一行一个正整数表示答案。

输入样例

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

输出数据

11100101

提示

$1 \le N,M \le 100000$ $1 \le u,v,x \le N$ $1 \le value[i],y\le 10000$ $0 \le k \le N-1$