No seu aniversário, Askhat recebeu de NurlashKO uma árvore enraizada com $n$ vértices, numerados de $1$ a $n$. Uma árvore é um grafo conexo não orientado sem ciclos. A raiz da árvore é o vértice de número $1$. O vértice $v$ é um antepassado do vértice $u$ se $v$ estiver no caminho mínimo de $u$ até à raiz. O antepassado comum mais baixo de uma sequência de vértices $(x_1,x_2,\ldots,x_k)$ é o vértice mais afastado da raiz que é antepassado de $x_i$ para todo $1\le i\le k$, e é denotado por $\operatorname{lca}(x_1,x_2,\ldots,x_k)$.

Além do presente, NurlashKO preparou uma tarefa para Askhat. Primeiro, apresentou uma sequência de comprimento $m$, $(a_1,a_2,\ldots,a_m)$, em que cada número é um vértice da árvore. A sequência pode conter vértices repetidos. Depois começou a fazer $q$ consultas, cada uma de um dos dois tipos:

• $1\ pos\ v$: NurlashKO pede a Askhat que altere o valor na posição $pos$ para $v$, ou seja, $a_{pos}=v$.
• $2\ l\ r\ v$: NurlashKO pede a Askhat que encontre um par $(x,y)$ tal que $l\le x\le y\le r$ e $\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$, ou que diga que esse par não existe.

Askhat passou muito tempo a investigar o presente e agora quer a tua ajuda.

Entrada

A primeira linha contém três inteiros positivos $n,m,q$: o tamanho da árvore, o comprimento da sequência e o número de consultas. As $n-1$ linhas seguintes contêm as arestas da árvore $(u_i,v_i)$ ($u_i\ne v_i$). A linha seguinte contém $m$ inteiros $a_1,a_2,\ldots,a_m$ ($1\le a_i\le n$): a sequência que NurlashKO ofereceu a Askhat. Cada uma das $q$ linhas seguintes descreve uma consulta. Se o primeiro número da consulta for $1$, seguem-se dois números $pos$ e $v$ ($1\le pos\le m$, $1\le v\le n$), que descrevem uma consulta do primeiro tipo. Se o primeiro número for $2$, seguem-se três números $l,r,v$ ($1\le l\le r\le m$, $1\le v\le n$), que descrevem uma consulta do segundo tipo. É garantido que, entre as $q$ consultas, pelo menos uma é do segundo tipo.

Saída

Para cada consulta do segundo tipo, imprime dois números $x$ e $y$, a resposta à consulta. Se não houver solução, imprime -1 -1 (sem aspas). Se houver várias soluções, imprime qualquer uma delas.

Subtarefas

Esta tarefa é composta por quatro subtarefas; em cada uma delas, os testes respeitam as restrições do enunciado:

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

Exemplos

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

Saída 1

1 3
3 3
-1 -1

Nota

• Sequência: $[4,5,2,3]$.
• Subsegmento $=[4,5,2]$, $v=1$. $\operatorname{lca}(4,5,2)=1$, resposta: $(1,3)$.
• Consulta de alteração, nova sequência: $[4,5,5,3]$.
• Subsegmento $=[5,3]$, $v=5$. $\operatorname{lca}(5)=5$, resposta: $(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$. Não existe solução.