Se le proporciona un árbol con raíz compuesto por ~n~ nodos. Los nodos están numerados ~1,2,\ldots,n~, y el nodo ~1~ es la raíz. 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. Calcular la suma de los valores en el subárbol del nodo ~s~.

Entrada

• La primera línea de entrada contiene dos enteros ~n~ y ~q~: el número de nodos y consultas. Los nodos están numerados ~1,2,\ldots,n~.
• La siguiente línea tiene ~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~.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada consulta tiene la forma "~1~ ~s~ ~x~" o "~2~ ~s~".

Salida

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

Restricciones

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

Ejemplo de Entrada

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

Ejemplo de Salida

8
10