给定一棵点数为 N 的树，顶点从1到N编号，以点 1 为根，每个点有权值。

对树进行 M个操作，操作有三种：

操作 1 ：把节点 x 的点权增加 a 。

操作 2 ：把以节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 ：询问节点 x 到根的路径中所有点的点权和。

第一行包含两个整数N, M(1 \le N, M \le 10^5)。

接下来一行 N 个整数，表示树中节点的初始权值。

接下来 N-1 行每行两个正整数a, b(1 \le a, b \le N)，表示该树中存在一条边 (a, b)。

接下来 M 行，每行表示一次操作：

其中第一个数表示该操作的种类(1-3)，之后接这个操作的参数(x 或者 x a)。

1 \le x \le N, |a| \le 10^6，所有输入均为整数且绝对值不超过10^6。

对于第3种操作，输出路径上的点权之和。