Askhat erhielt von NurlashKO zum Geburtstag einen gewurzelten Baum mit $n$ Knoten, die von $1$ bis $n$ nummeriert sind. Ein Baum ist ein zusammenhängender ungerichteter Graph ohne Zyklen. Die Wurzel des Baums ist der Knoten mit der Nummer $1$. Ein Knoten $v$ ist ein Vorfahr eines Knotens $u$, wenn $v$ auf dem kürzesten Pfad von $u$ zur Wurzel liegt. Der tiefste gemeinsame Vorfahr einer Folge von Knoten $(x_1,x_2,\ldots,x_k)$ ist der von der Wurzel am weitesten entfernte Knoten, der für alle $1\le i\le k$ ein Vorfahr von $x_i$ ist; er wird mit $lca(x_1,x_2,\ldots,x_k)$ bezeichnet.

Zusätzlich zum Geschenk bereitete NurlashKO eine Aufgabe für Askhat vor. Zuerst gab er eine Folge der Länge $m$ an: $(a_1,a_2,\ldots,a_m)$. Jede Zahl in der Folge ist ein Knoten des Baums. Knoten dürfen in der Folge mehrfach vorkommen. Dann stellte er $q$ Anfragen, jede von einem der folgenden beiden Typen:

• 1 pos v: NurlashKO bittet Askhat, den Wert an Position $pos$ in $v$ zu ändern, also $a_{pos}=v$ zu setzen.
• 2 l r v: NurlashKO bittet Askhat, ein Paar $(x,y)$ zu finden, für das $l\le x\le y\le r$ und $lca(a_x,a_{x+1},\ldots,a_y)=v$ gelten, oder anzugeben, dass es kein solches Paar gibt.

Askhat hat viel Zeit damit verbracht, das Geschenk zu untersuchen, und möchte nun deine Hilfe.

Eingabe

Die erste Eingabezeile enthält drei positive ganze Zahlen $n,m,q$: die Größe des Baums, die Länge der Folge und die Anzahl der Anfragen. Die nächsten $n-1$ Zeilen enthalten die Kanten des Baums $(u_i,v_i)$ mit $u_i\ne v_i$. Die nächste Zeile enthält $m$ ganze Zahlen $a_1,a_2,\ldots,a_m$ mit $1\le a_i\le n$: die Folge, die NurlashKO Askhat geschenkt hat. Jede der nächsten $q$ Zeilen beschreibt eine Anfrage. Ist die erste Zahl der Anfrage $1$, folgen zwei Zahlen $pos,v$ mit $1\le pos\le m$ und $1\le v\le n$: eine Anfrage des ersten Typs. Ist die erste Zahl $2$, folgen drei Zahlen $l,r,v$ mit $1\le l\le r\le m$ und $1\le v\le n$: eine Anfrage des zweiten Typs. Es ist garantiert, dass unter den $q$ Anfragen mindestens eine vom zweiten Typ ist.

Ausgabe

Gib für jede Anfrage des zweiten Typs zwei Zahlen $x,y$ als Antwort aus. Falls es keine Lösung gibt, gib -1 -1 ohne Anführungszeichen aus. Gibt es mehrere Lösungen, darfst du eine beliebige ausgeben.

Teilaufgaben

Diese Aufgabe besteht aus vier Teilaufgaben. In jeder Teilaufgabe erfüllen die Tests die Bedingungen der Aufgabenstellung:

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

Beispiele

Eingabe 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

Ausgabe 1

1 3
3 3
-1 -1

Hinweis

• Folge: $[4,5,2,3]$.
• Teilabschnitt $=[4,5,2]$, $v=1$. $lca(4,5,2)=1$, Antwort: $(1,3)$.
• Änderungsanfrage, neue Folge: $[4,5,5,3]$.
• Teilabschnitt $=[5,3]$, $v=5$. $lca(5)=5$, Antwort: $(3,3)$.
• Teilabschnitt $=[4,5,5]$, $v=1$. $lca(4)=4$, $lca(5)=5$, $lca(4,5)=3$, $lca(5,5)=5$, $lca(4,5,5)=3$. Es gibt keine Lösung.