$N$ sommets d'un arbre (graphe connexe sans cycle non orienté). Les sommets sont numérotés de $1$ à $N$, et les arêtes sont numérotées de $1$ à $N-1$. Chaque sommet a un poids.

Écrivez un programme qui effectue les deux requêtes suivantes.

1 u v : calcule et affiche la somme maximale d'une sous-séquence contiguë (éventuellement vide, donc la réponse est supérieure ou égale à $0$) sur le chemin de $u$ à $v$. 2 u v w : remplace le poids de tous les sommets sur le chemin de $u$ à $v$ par $w$.

Entrée

La première ligne contient $N$ ($2 \le N \le 100\,000$).

La deuxième ligne contient les poids des sommets dans l'ordre du sommet $1$ au sommet $N$.

Les $N-1$ lignes suivantes contiennent deux entiers $u$ et $v$, les deux sommets reliés par l'arête $i$ ($1 \le i \le N-1$).

La ligne suivante contient le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes contiennent une requête par ligne.

Les poids des sommets sont des entiers dont la valeur absolue est inférieure ou égale à $10\,000$.

Sortie

Pour chaque requête, affichez le résultat sur une ligne distincte, dans l'ordre des requêtes.

Exemples

Entrée 1

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

Sortie 1

5
9