Frondy y Christopher estaban un día cualquiera explorando en la UCI, sin embargo, se quedaron perdidos y llamaron a su grandioso amigo Norge para que los fuera a buscar.

Mientras tanto, a Christopher se le ocurrió el siguiente problema:

Un árbol de ~n~ nodos y enraizado en el nodo ~1~ tiene un valor ~a_i~ en el nodo ~i~. Debe procesar ~q~ consultas de ~3~ tipos distintos:

• 1 u x: debe sumarle ~x~ al valor de cada ancestro* del nodo ~u~.
• 2 u x: debe asignarle ~x~ al valor del nodo ~u~, es decir ~a_u := x~.
• 3 u k: debe responder con el valor actual del ~k~-ésimo ancestro del nodo ~u~. El ~k~-ésimo ancestro del nodo ~u~ es su ancestro a distancia ~k~.

* Un nodo ~v~ se considera ancestro de un nodo ~u~ si ~v~ pertenece al camino desde la raíz del árbol hasta ~u~. Note que ~u~ se considera ancestro de sí mismo.

Frondy y Christopher lograron resolver el problema rápidamente, así que se lo comentaron a su amigo Norge cuando llegó para desafiarlo. Sin embargo, Norge, como había pasado una madrugada muy ocupado, decide regalarle el problema a usted.

Entrada

La primera línea de entrada contiene dos enteros ~n~ y ~q~ (~1 \le n, q \le 2\cdot10^5~), la cantidad de nodos del árbol y la cantidad de consultas respectivamente.

La segunda línea de entrada contiene ~n-1~ enteros ~p_2, p_3, \dots, p_n~, donde ~p_i~ representa el padre del nodo ~i~.

La tercera línea de entrada contiene ~n~ enteros ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) para cada ~i~ desde ~1~ hasta ~n~.

Siguen ~q~ líneas, donde en cada una se le dará inicialmente un entero ~op~, que indica el tipo de consulta. Debe leer en caso de ser ~op~ de tipo:

1. ~u~ ~x~ (~1 \le u \le n~) (~1 \le x \le 10^9~).
2. ~u~ ~x~ (~1 \le u \le n~) (~1 \le x \le 10^9~).
3. ~u~ ~k~ (~1 \le u \le n~) (~0 \le k < n~).

Salida

Imprima para cada consulta donde ~op = 3~: un único entero, el valor actual del ~k_i~-ésimo ancestro del nodo ~u_i~.

Puntuación

Subtarea	Condiciones	Puntos	Dependencias
~1~	~1 \le n, q \le 3000~	~10~	~-~
~2~	~p_i = i-1~ para todo ~i~	~15~	~-~
~3~	No habrán operaciones de tipo 1	~20~	~1, 2~
~4~	No habrán operaciones de tipo 2	~20~	~1, 2~
~5~	~-~	~35~	~3, 4~

Ejemplos

Entrada de ejemplo 1

4 3
1 1 3
176 15 169 45
2 1 199
3 1 0
3 4 0

Salida de ejemplo 1

199
45

Entrada de ejemplo 2

10 20
1 1 5 9 9 3 5 3 3
115 49 171 59 85 33 59 4 39 160
2 5 22
3 3 0
2 9 137
1 4 59
3 8 0
2 4 192
1 10 38
1 5 109
2 5 161
2 3 6
3 3 0
1 1 3
2 1 55
1 9 50
3 8 0
2 4 76
3 2 0
2 2 33
2 2 59
3 7 2

Salida de ejemplo 2

171
4
6
4
49
105