Askhat otrzymał od NurlashKO na urodziny ukorzenione drzewo o $n$ wierzchołkach, ponumerowanych od $1$ do $n$. Drzewo to spójny graf nieskierowany bez cykli. Korzeniem drzewa jest wierzchołek o numerze $1$. Wierzchołek $v$ jest przodkiem wierzchołka $u$, jeśli $v$ leży na najkrótszej ścieżce z $u$ do korzenia. Najniższy wspólny przodek ciągu wierzchołków $(x_1,x_2,\ldots,x_k)$ to najbardziej oddalony od korzenia wierzchołek, który jest przodkiem $x_i$ dla każdego $1\le i\le k$; oznaczamy go przez $\operatorname{lca}(x_1,x_2,\ldots,x_k)$.

Oprócz prezentu NurlashKO przygotował dla Askhata zadanie. Najpierw podał ciąg długości $m$ — $(a_1,a_2,\ldots,a_m)$, w którym każda liczba jest wierzchołkiem drzewa. Wierzchołki mogą powtarzać się w ciągu. Następnie zaczął zadawać $q$ zapytań, z których każde jest jednego z dwóch typów:

• $1\ \mathit{pos}\ v$ — NurlashKO prosi Askhata o zmianę wartości na pozycji $\mathit{pos}$ na $v$, czyli $a_{\mathit{pos}}=v$.
• $2\ l\ r\ v$ — NurlashKO prosi Askhata o znalezienie pary $(x,y)$ takiej, że $l\le x\le y\le r$ oraz $\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$, albo stwierdzenie, że taka para nie istnieje.

Askhat poświęcił już dużo czasu na badanie prezentu i teraz potrzebuje twojej pomocy.

Wejście

Pierwszy wiersz zawiera trzy dodatnie liczby całkowite $n,m,q$ — rozmiar drzewa, długość ciągu i liczbę zapytań. Kolejnych $n-1$ wierszy zawiera krawędzie drzewa $(u_i,v_i)$ ($u_i\ne v_i$). Następny wiersz zawiera $m$ liczb całkowitych $a_1,a_2,\ldots,a_m$ ($1\le a_i\le n$) — ciąg podarowany Askhatowi przez NurlashKO. Każdy z kolejnych $q$ wierszy opisuje zapytanie. Jeśli pierwsza liczba zapytania jest równa $1$, następują po niej dwie liczby $\mathit{pos}$ i $v$ ($1\le\mathit{pos}\le m$, $1\le v\le n$) — zapytanie pierwszego typu. Jeśli pierwsza liczba zapytania jest równa $2$, następują po niej trzy liczby $l,r,v$ ($1\le l\le r\le m$, $1\le v\le n$) — zapytanie drugiego typu. Gwarantujemy, że spośród $q$ zapytań co najmniej jedno jest drugiego typu.

Wyjście

Dla każdego zapytania drugiego typu wypisz dwie liczby $x$ i $y$ — odpowiedź na to zapytanie. Jeśli rozwiązanie nie istnieje, wypisz -1 -1 (bez cudzysłowów). Jeśli rozwiązań jest wiele, wypisz dowolne z nich.

Podzadania

Zadanie składa się z czterech podzadań; w każdym z nich testy spełniają ograniczenia podane w treści:

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

Przykład

Wejście 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

Wyjście 1

1 3
3 3
-1 -1

Uwagi

• Ciąg: $[4,5,2,3]$.
• Podprzedział $=[4,5,2]$, $v=1$. $\operatorname{lca}(4,5,2)=1$, odpowiedź: $(1,3)$.
• Zapytanie zmiany, nowy ciąg: $[4,5,5,3]$.
• Podprzedział $=[5,3]$, $v=5$. $\operatorname{lca}(5)=5$, odpowiedź: $(3,3)$.
• Podprzedział $=[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$. Rozwiązanie nie istnieje.