说明

在很久很久以前，有一棵 $n$ 个点的树，每个点有一个点权。

现在有 $q$ 次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。

（题目不是很好懂，没看太懂的可以看看样例解释）

输入格式

第一行两个整数 $n,q$。

接下来 $n-1$ 行每行两个整数 $a$ 和 $b$，表示树中 $a$ 与 $b$ 之间有一条边，保证给出的边不会重复。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的点权。

接下来 $q$ 行每行两或三个数，如果第一个数为 $1$，那么接下来有两个数 $x$ 和 $y$，表示将第 $x$ 个点的点权修改为 $y$，如果第一个数为 $2$，那么接下来有一个数 $x$，表示询问以 $x$ 为根时每棵子树点权和的平方和。

输出格式

对于每个询问输出答案。

4 5
1 2
2 3
2 4
4 3 2 1
2 2
1 1 3
2 3
1 2 4
2 4

121
140
194

提示

样例解释

这是一个菊花图，$2$ 与 $1,3,4$ 间有边。

一开始每个点点权分别为 $4,3,2,1$。

第一个询问以 $2$ 为根，$1,3,4$ 子树中都只有本身一个点，$2$ 子树中有所有点，那么 $1,3,4$ 子树中的点权和就分别是自己的点权 $4,2,1$，$2$ 子树中的点权和就是 $4+3+2+1=10$，$4^2+2^2+1^1+10^2=121$。

接下来将第一个点点权修改为 $3$，每个点点权分别为 $3,3,2,1$。

第二个询问以 $3$ 为根，$1,4$ 子树中只有自己，$2$ 子树中有 $1,2,4,3$ 子树中有所有点，$1,4$ 子树点权和就是自己的点权 $3,1$，$2$ 子树点权和就是 $3+3+1=7$，$3$ 子树点权和为 $3+3+2+1=9$，$3^2+1^2+7^2+9^2=140$。

接下来把第二个点点权修改为 $4$，每个点点权分别为 $3,4,2,1$。

第三个询问以 $4$ 为根，$1,3$ 子树点权和就是 $3$ 和 $2$，$2$ 子树点权和就是 $3+4+2=9$，$4$ 子树点权和为 $3+4+2+1=10$，$3^2+2^2+9^2+10^2=194$。

数据范围

对于 $10\%$ 的数据，$n,q \leq 2000$。

对于 $40\%$ 的数据，$n,q \leq 6\times 10^4$。

对于另外 $30\%$ 的数据，保证每次询问的根都为 $1$。

对于 $100\%$ 的数据，$1 \leq n,q \leq 2\times 10^5$，$-10 \leq$ 输入的每个点权 $\leq 10$。

建议使用输入优化，虽然标程没加读入优化也能过。