Se le da un árbol enraizado que consta de ~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 valores en el camino de la raíz al nodo ~s~

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~ ~s~".

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
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4

Ejemplo de Salida

11
8