小 H 居住的国度形成一棵树。树是 $n$ 个点 $n-1$ 条边的连通图，每一个节点上是一个城市，编号为 $i$ 的城市内居住着一位小朋友，这位小朋友期待在万圣节收到 $a_i$ 颗糖果。

作为万圣老人，小 H 将计划他的万圣节行程，一种可能的行程是携带 $m$ 个糖果从编号为 $u$ 的城市出发，通过唯一的最短路走向 $v$ 号城市，并给予居住在这条路径上（包括 $u, v$）的所有小朋友一些糖果（可能某些小朋友没有收到糖果）。

在小 H 分发糖果之后，所有的小朋友（包括路径之外的）将会把收到的糖果数量 $a'_i$ 与自己期待的糖果数量 $a_i$ 进行比较，称一位小朋友的悲哀度为

$$\max\{0, a_i - a'_i\}^2$$

那么小 H 希望最小化所有小朋友的悲哀度之和。

现在按照时间顺序，依次发生 $q$ 个事件。每个事件有以下两种可能：

• 1 u b：居住在 $u$ 号节点的小朋友改变了主意，将他期待收到的糖果数量变为 $b$，也即将 $a_i$ 赋值为 $b$。注意这个过程会影响后续的事件。
• 2 u v m：小 H 模拟一个万圣节行程计划，请你告诉他最小可能的悲哀度总和是多少。注意这个过程不会影响后续的事件。

输入格式

第一行两个正整数 $n, q$ 表示城市个数与事件个数。

接下来 $n-1$ 行，每行两个正整数 $u, v$ 表示树的一条边。保证不会重复给出同一条边。

接下来一行 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$，表示每位小朋友期待的糖果数目。

接下来 $q$ 行每行可能为 1 u b 与 2 u v m 两种形式之一，含义如上所述。

输出格式

对于每一个第二类事件，输出一行一个非负整数表示最小的悲哀度总和。

样例一

input

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

output

3
6

限制与约定

对于所有数据，$1 \le n,q \le 10^5$, $0 \le a_i, b \le 10^9$, $0\le m \le 10^{14}$, $1 \le u, v \le n$。

子任务 1（$10\%$）：$n,q\le 1000, m\le 1000$。

子任务 2（$15\%$）：$n,q \le 1000$。

子任务 3（$15\%$）：树的形态是一条链，即树中每个节点的度数 $\le 2$。

子任务 4（$60\%$）：无特殊限制。