Hay un árbol (grafo conexo no dirigido sin ciclos) formado por $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$. Cada vértice tiene un peso.

Escriba un programa que realice las siguientes dos consultas:

• 1 u v: Calcule e imprima la suma máxima de un subsegmento contiguo (puede estar vacío, por lo que la respuesta es mayor o igual que $0$) en el camino de $u$ a $v$.
• 2 u v w: Cambie el peso de todos los vértices en el camino de $u$ a $v$ a $w$.

Entrada

La primera línea contiene $N$ ($2 \le N \le 100{,}000$).

La segunda línea contiene los pesos de los vértices en orden desde el vértice $1$.

Las siguientes $N-1$ líneas contienen dos números $u$ y $v$ que representan los vértices conectados por la arista $i$.

La siguiente línea contiene el número de consultas $M$ ($1 \le M \le 100{,}000$).

Las siguientes $M$ líneas contienen las consultas, una por línea.

Los pesos de los vértices son enteros con valor absoluto menor o igual a $10{,}000$.

Salida

Imprima los resultados de cada consulta en orden, uno por línea.

Ejemplos

Entrada 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

Salida 1

5
9