Can you answer these queries VII

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem

Each vertex of a tree stores an integer. Support assigning one value to every vertex on a path and querying the maximum contiguous subarray sum along a path. The empty subarray is allowed, so the answer is never negative.

Input

The first line contains $n$. The second line contains the $n$ initial values. The next $n-1$ lines contain the tree edges. The next line contains $q$. Each of the following $q$ operations is:

• 1 a b: query the maximum contiguous subarray sum on the path from $a$ to $b$.
• 2 a b c: assign value $c$ to every vertex on the path from $a$ to $b$.

Output

For each operation of type 1, print the requested maximum subarray sum.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le10^5$.
• $|x_i|,|c|\le10000$.

Example

Input

1
2
5
1 1 1
1 1 1
2 1 1 18
2 1 1 -16
2 1 1 9

Output

2
2

Explanation

The first two operations are path queries and both see the initial value 2. The remaining operations only assign new values and therefore produce no output.