Askhat recibió de NurlashKO un árbol enraizado como regalo de cumpleaños, con $n$ vértices numerados del $1$ al $n$. Un árbol es un grafo no dirigido conexo sin ciclos. La raíz del árbol es el vértice número $1$. Un vértice $v$ es antepasado de un vértice $u$ si $v$ se encuentra en el camino mínimo de $u$ a la raíz. El antepasado común más bajo de una secuencia de vértices $(x_1,x_2,\ldots,x_k)$ es el vértice más alejado de la raíz que es antepasado de $x_i$ para todo $1\le i\le k$; se denota por $\operatorname{lca}(x_1,x_2,\ldots,x_k)$.

Además del regalo, NurlashKO preparó una tarea para Askhat. Primero le dio una secuencia de longitud $m$, $(a_1,a_2,\ldots,a_m)$, cuyos elementos son vértices del árbol. La secuencia puede contener vértices repetidos. Después empezó a plantear $q$ consultas, cada una de uno de los siguientes dos tipos:

• $1\ pos\ v$: NurlashKO pide a Askhat que cambie el valor en la posición $pos$ por $v$, es decir, $a_{pos}=v$.
• $2\ l\ r\ v$: NurlashKO pide a Askhat que encuentre un par $(x,y)$ tal que $l\le x\le y\le r$ y $\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$, o indique que no existe tal par.

Askhat ha dedicado mucho tiempo a estudiar el regalo y ahora quiere que le ayudes.

Entrada

La primera línea contiene tres enteros positivos $n$, $m$ y $q$: el tamaño del árbol, la longitud de la secuencia y el número de consultas. Las siguientes $n-1$ líneas contienen las aristas del árbol $(u_i,v_i)$ ($u_i\ne v_i$). La siguiente línea contiene $m$ enteros $a_1,a_2,\ldots,a_m$ ($1\le a_i\le n$), la secuencia que NurlashKO regaló a Askhat. Cada una de las siguientes $q$ líneas describe una consulta. Si el primer número de la consulta es $1$, le siguen dos números $pos$ y $v$ ($1\le pos\le m$, $1\le v\le n$): es una consulta del primer tipo. Si el primer número es $2$, le siguen tres números $l$, $r$ y $v$ ($1\le l\le r\le m$, $1\le v\le n$): es una consulta del segundo tipo. Se garantiza que al menos una de las $q$ consultas es del segundo tipo.

Salida

Para cada consulta del segundo tipo, imprime dos números $x$ e $y$ que sean su respuesta. Si no existe solución, imprime -1 -1 (sin comillas). Si hay varias soluciones, imprime cualquiera de ellas.

Subtareas

Este problema consta de cuatro subtareas; en cada una, los casos de prueba cumplen las restricciones del enunciado:

1. $1\le n,m,q\le100$. Vale 12 puntos.
2. $1\le n,m,q\le500$. Vale 18 puntos.
3. $1\le n,m,q\le2000$. Vale 26 puntos.
4. $1\le n,m,q\le2\cdot10^5$. Vale 44 puntos.

Ejemplos

Entrada 1

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

Salida 1

1 3
3 3
-1 -1

Nota

• Secuencia: $[4,5,2,3]$.
• Subsegmento $=[4,5,2]$, $v=1$. $\operatorname{lca}(4,5,2)=1$, respuesta: $(1,3)$.
• Consulta de modificación; la nueva secuencia es $[4,5,5,3]$.
• Subsegmento $=[5,3]$, $v=5$. $\operatorname{lca}(5)=5$, respuesta: $(3,3)$.
• Subsegmento $=[4,5,5]$, $v=1$. $\operatorname{lca}(4)=4$, $\operatorname{lca}(5)=5$, $\operatorname{lca}(4,5)=3$, $\operatorname{lca}(5,5)=5$, $\operatorname{lca}(4,5,5)=3$. No existe solución.