There is a tree (an undirected connected graph with no cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Each vertex has a weight.

Write a program that processes the following two types of queries:

• 1 u v: Compute the maximum subarray sum on the path from $u$ to $v$ (the answer is non-negative because the subarray may be empty).
• 2 u v w: Change the weights of all vertices on the path from $u$ to $v$ to $w$.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$).

The second line contains the weights of the vertices in order from vertex $1$ to vertex $N$.

The next $N-1$ lines each contain two integers $u$ and $v$ representing the two vertices connected by the $i$-th edge.

The next line contains $M$ ($1 \le M \le 100{,}000$), the number of queries.

The next $M$ lines each contain one query.

The absolute value of each vertex weight is an integer less than or equal to $10{,}000$.

Output

Output the result of each query in order, one per line.

Examples

Input

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

Output

5
9