GSS7 - Can you answer these queries VII


Given a tree with N (N <= 100000) nodes. Each node has a interger value x_i (|x_i| <= 10000).

You have to apply Q (Q <= 100000) operations:

1. 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. 2 a b c : change all value in the path a->b ( inclusive ) to c. (|c| <= 10000)

Input

first line consists one interger N.

next line consists N interger x_i.

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

next line consists 1 interger 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

hide comments
DK...: 2017-11-04 16:03:34

it's not necesary to use scanf/printf, simple fast I/O got AC

weramajstor: 2017-01-15 23:52:24

Like Dante said,"You who enter leave all your hope behind!"

Ghost Of Perdition: 2014-01-24 05:09:39

very hard-implementation problem !!!!


Added by:刘启鹏
Date:2010-06-14
Time limit:0.200s-0.570s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:my own problems