题目描述

给定一棵树，设计数据结构支持以下操作：

1. $1\ u\ v\ d$：表示将路径 $(u,v)$ 加 $d$。
2. $2\ u\ v$：表示询问路径 $(u,v)$ 上点权绝对值的和。

输入格式

第一行包含两个整数$n$和$m$，表示结点个数和操作数。

接下来一行包含$n$个整数 $a_i$，表示点$i$的权值。

接下来$n-1$行，每行两个整数$u,v$表示存在一条$(u,v)$的边。

接下来$m$行，每行一个操作，输入格式见题目描述。

输出格式

对于每个询问输出答案。

输入样例

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

输出样例

10
13
9

提示

对于$100\%$的数据，$n,m \le 10^5$，且 $0 \le d,|a_i| \le 10^8$