Dane jest drzewo (spójny graf nieskierowany bez cykli) składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Każdy wierzchołek ma wagę.

Napisz program wykonujący następujące dwa rodzaje zapytań:

• 1 u v: Znajdź i wypisz maksymalną sumę spójnego podciągu (może być pusty, więc odpowiedź jest nieujemna) na ścieżce od $u$ do $v$.
• 2 u v w: Ustaw wagę wszystkich wierzchołków na ścieżce od $u$ do $v$ na $w$.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \le N \le 100\,000$).

Drugi wiersz zawiera wagi wierzchołków w kolejności od wierzchołka $1$ do $N$.

Trzeciego wiersza i kolejne $N-1$ wierszy zawierają dwie liczby $u$ i $v$ oznaczające, że krawędź $i$ łączy wierzchołki $u$ i $v$.

Następny wiersz zawiera liczbę zapytań $M$ ($1 \le M \le 100\,000$).

Kolejne $M$ wierszy zawiera po jednym zapytaniu.

Wagi wierzchołków są liczbami całkowitymi, których wartość bezwzględna nie przekracza $10\,000$.

Wyjście

Dla każdego zapytania wypisz wynik w osobnym wierszu, w kolejności występowania zapytań.

Przykład

Wejście

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

Wyjście

5
9