题目描述

给定一个包含 $n$ 个节点的树。节点编号从 $1$ 到 $n$。

初始时，每个节点都有一个权值，节点 $i$ 的权值为 $a_i$。

接下来有 $q$ 次操作，操作分为如下两种类型：

• $\mathtt{1\ p\ k}$：将节点 $p$ 的权值修改为 $x$（即：$a_p \leftarrow x$）；
• $\mathtt{2\ x\ y}$：查询从节点 $x$ 到节点 $y$ 的简单路径上的所有节点的权值和。

输入格式

第一行，两个整数 $n$ 和 $q$，以空格分隔，分别表示树的大小以及操作次数（$1 \le n, q \le 2 \cdot 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$，表示初始时每个节点的权值。

接下来 $n-1$ 行，每行包含两个整数，表示树上一条边连接的两个节点的编号。

接下来 $q$ 行，每行包含一个操作（$1 \le p,x,y \le n; 1 \le k \le 10^9$）。

输出格式

对于每次查询操作，输出一行，包含一个整数，表示对应的结果。

样例

5 5
1 2 3 4 5
1 2
2 3
2 4
4 5
2 1 3
1 2 6
2 1 3
1 4 7
2 1 5

6
10
19

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n, q \le 20; a_i, k \le 10^3$
• 对于 $60\%$ 的数据，$n, q \le 2000; a_i, k \le 10^6$
• 对于 $100\%$ 的数据，$1 \le n, q \le 2 \cdot 10^5; 1 \le a_i, k \le 10^9$