Given a tree with N (N ≤ 100000) nodes. Each node has a integer value x_i (|x_i| ≤ 10000).

You have to apply Q (Q ≤ 100000) operations:

• 1 a b : answer the maximum contiguous sum (maybe empty, will always larger than or equal to 0) from the path a→b (inclusive).
• 2 a b c : change all value in the path a→b (inclusive) to c. (|c| ≤ 10000)

Input

first line consists one integer N.

next line consists N integer x_i.

next N-1 line, each consists two integer u, v, means that node u and node v are connected

next line consists 1 integer Q.

next Q line: 1 a b or 2 a b c.

Output

For each query, output one line the maximum contiguous sum.

Example

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