Askhat 在生日時收到了 NurlashKO 送的一棵有根樹作為禮物，樹有 $n$ 個頂點，編號為 $1$ 到 $n$。樹是沒有任何環的連通無向圖。樹根是編號為 $1$ 的頂點。如果頂點 $v$ 位於從 $u$ 到樹根的最短路徑上，則 $v$ 是 $u$ 的祖先。一個頂點序列 $(x_1,x_2,\ldots,x_k)$ 的最近共同祖先，是距離樹根最遠且對所有 $1\le i\le k$ 都是 $x_i$ 的祖先的頂點，記為 $\operatorname{lca}(x_1,x_2,\ldots,x_k)$。

除了禮物以外，NurlashKO 還為 Askhat 準備了一道題目。首先，他給出了一個長度為 $m$ 的序列 $(a_1,a_2,\ldots,a_m)$，序列中的每個數都是樹上的一個頂點。序列中可以出現重複的頂點。然後，他開始提出 $q$ 次詢問，每次詢問屬於以下兩種類型之一：

• $1\ pos\ v$：NurlashKO 要求 Askhat 將位置 $pos$ 的值改為 $v$，也就是 $a_{pos}=v$。
• $2\ l\ r\ v$：NurlashKO 要求 Askhat 找出一對 $(x,y)$，滿足 $l\le x\le y\le r$ 且 $\operatorname{lca}(a_x,a_{x+1},\ldots,a_y)=v$，或說明不存在這樣的一對數。

Askhat 已經花了許多時間研究這份禮物，現在他希望得到你的幫助。

輸入格式

第一行包含三個正整數 $n,m,q$，分別表示樹的大小、序列的長度和詢問的數量。接下來 $n-1$ 行包含樹的邊 $(u_i,v_i)$（$u_i\ne v_i$）。接下來一行包含 $m$ 個整數 $a_1,a_2,\ldots,a_m$（$1\le a_i\le n$），表示 NurlashKO 送給 Askhat 的序列。接下來 $q$ 行，每行描述一次詢問。如果詢問的第一個數是 $1$，後面會有兩個數 $pos,v$（$1\le pos\le m$, $1\le v\le n$），表示第一類詢問。如果第一個數是 $2$，後面會有三個數 $l,r,v$（$1\le l\le r\le m$, $1\le v\le n$），表示第二類詢問。保證 $q$ 次詢問中至少有一次是第二類詢問。

輸出格式

對每次第二類詢問，輸出兩個數 $x,y$ 作為答案。如果無解，輸出 -1 -1（不含引號）。如果有多組解，輸出任意一組。

子任務

本題包含四個子任務，各子任務的測試資料均滿足題目敘述中的限制：

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

範例

輸入格式 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

輸出格式 1

1 3
3 3
-1 -1

說明

• 序列：$[4,5,2,3]$。
• 子區間為 $[4,5,2]$，$v=1$。$\operatorname{lca}(4,5,2)=1$，答案為 $(1,3)$。
• 修改詢問，新的序列為 $[4,5,5,3]$。
• 子區間為 $[5,3]$，$v=5$。$\operatorname{lca}(5)=5$，答案為 $(3,3)$。
• 子區間為 $[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$。無解。