题目描述

C 国有一个庞大的铁路网。

这个铁路网由 $N$ 个城市和 $N-1$ 条铁路线组成，每条铁路线连接两个城市（即构成一棵树）。令城市 $1$ 为首都（即根节点）。

城市 $i$ 有 $a_i$ 个人。他们平时要到其它城市和别人见面。铁路公司准备研究各条铁路线的便利度。但是 C 国的人口流动也非常严重，一个城市随时会增加或减少人口，但不会小于 $0$。为此，铁路公司也会随时改变铁路线的位置，但保证修改后整个铁路网依旧是一棵树。

一条铁路线的交流便利度为树上路过它的交流路径的数量。（交流路径为简单路径）

其中从 $x$ 到 $y$ 的交流路径的数量有 $a_x \times a_y$ 条。

现在给你 $Q$ 个时间节点，每个时间节点的事件如下：

add x k 城市 $x$ 的人口增加了 $k$（$k$ 有可能是负数）。

query x y 求连接城市 $x$ 和城市 $y$ 的铁路线的交流便利度。

change x y a b 铁路公司切断了 $x$ 和 $y$ 之间的铁路线，并修建了一条从 $a$ 到 $b$ 的铁路线。保证修改后整个铁路网依旧是一棵树。

输入格式

第一行两个整数 $N,Q$。

第二行 $N$ 个整数 $a_1,a_2 … a_N$。

下来 $N-1$ 行，每行两个整数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间有一条铁路线。

下面 $Q$ 行询问，见题意。

输出格式

对于每一个 query 操作，输出一行表示答案。

输入输出样例 #1

输入 #1

5 5
3 0 9 2 7
1 3
1 2
2 4
1 5
change 4 2 4 5
add 5 2
query 4 1
change 2 1 2 3
query 1 5

输出 #1

42
132

说明/提示

$1 \leq N,Q \leq 2 \times 10^4,0 \leq a_i \leq 10^5$。