题目描述

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

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

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

• $\mathtt{1\ x\ y\ k}$：将从节点 $x$ 到节点 $y$ 的简单路径上的每个节点的权值都加上 $k$；
• $\mathtt{2\ x\ y}$：查询从节点 $x$ 到节点 $y$ 的简单路径上的节点权值的最大值；
• $\mathtt{3\ x\ y}$：查询从节点 $x$ 到节点 $y$ 的简单路径上的节点权值的最小值；
• $\mathtt{4\ x\ y}$：查询从节点 $x$ 到节点 $y$ 的简单路径上的所有节点的权值和。

输入格式

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

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

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

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

输出格式

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

样例

7 6
1 3 -2 4 -1 5 8
1 2
1 3
2 4
2 5
4 6
3 7
2 3 5
1 1 5 3
2 3 5
1 3 6 -2
3 2 6
4 1 7

3
6
2
6

说明/提示

数据规模与约定

对于 $100\%$ 的数据，$1 \le n, q \le 2 \cdot 10^5$, $1 \le x, y \le n, -10^6 \le k \le 10^6$.