给定一棵由 $N$ 个顶点组成的树（无向无环连通图）。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。每个顶点都有一个权值。

请编写一个程序，执行以下两种查询：

• 1 u v：输出从 $u$ 到 $v$ 的路径上的最大连续子段和（路径可以为空，因此答案大于等于 $0$）。
• 2 u v w：将 $u$ 到 $v$ 路径上的所有顶点的权值修改为 $w$。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 100{,}000$）。

第二行按顺序给出从 $1$ 号顶点到 $N$ 号顶点的权值。

接下来 $N-1$ 行，每行包含两个整数 $u$ 和 $v$，表示第 $i$ 条边连接的两个顶点编号。

下一行包含一个整数 $M$（$1 \le M \le 100{,}000$），表示查询的个数。

接下来 $M$ 行，每行给出一个查询。

每个顶点的权值都是绝对值不超过 $10{,}000$ 的整数。

输出格式

对于每个查询，按顺序在一行中输出结果。

样例

输入

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

输出

5
9