Se le da un árbol formado por ~n~ nodos. Los nodos están numerados ~1,2,\ldots,n~. Cada nodo tiene un valor.

Su tarea consiste en procesar los siguientes tipos de consultas:

1. Cambiar el valor del nodo ~s~ a ~x~.
2. Encontrar el valor máximo en el camino entre los nodos ~a~ y ~b~.

Entrada

La primera línea de entrada contiene dos números enteros ~n~ y ~q~: el número de nodos y de consultas. Los nodos se numeran ~1,2,\ldots,n~.

La siguiente línea contiene ~n~ enteros ~v_1,v_2,\ldots,v_n~: el valor de cada nodo.

Luego hay ~n-1~ líneas que describen las aristas. Cada línea contiene dos enteros ~a~ y ~b~: hay una arista entre los nodos ~a~ y ~b~.

Por último, hay q líneas que describen las consultas. Cada consulta tiene la forma "~1~ ~s~ ~x~" o "~2~ ~a~ ~b~".

Salida

Imprime la respuesta a cada consulta de tipo ~2~.

Restricciones

• ~1 \le n, q \le 2 \cdot 10^5~
• ~1 \le a,b, s \le n~
• ~1 \le v_i, x \le 10^9~

Ejemplo de Entrada

5 3
2 4 1 3 3
1 2
1 3
2 4
2 5
2 3 5
1 2 2
2 3 5

Ejemplo de Salida

4 3