問題文

JOI国には$N$ 個の町がある。これらの町には活気という値が定まっている。$i$ 番目の町の活気は $C_i$ である。
また、これらの町は $N-1$ 本の一方向にしか行くことのできない道でつながっている。$i$本目の辺は町$E_i$と$F_i$をこの向きに結んでいる。
JOI国は頂点$1$ を根とする根付き木となっていて、全ての辺は根の方向へ向き付けられている。

ビ太郎は、こんなJOI国に住む一匹のビーバーであり、パーティーが大好きである。ビ太郎の番号は $1$ である。
また、彼には $2$ ～ $K$ までの番号が付いた $K-1$ 人の親族がいて、彼らも全員パーティーが大好きである。
最初、 $i$ 番目のビーバーは町 $A_i$ に住んでいる。

ビ太郎達は定期的に、以下の条件を満たすようにパーティーを開催する。

• パーティーには、$L \leq x \leq R$ を満たす番号のビーバーを招待する。
• 会場は、上記のすべてのビーバーにとって到達可能な町にする。
• 上の条件を満たす町のうち、活気が最大の町が選ばれる。
• パーティーが終了した後、すべてのビーバーはおうちに帰る。

• $T_i=1$ の時 :　ビーバー $X_{i}$が町 $Y_{i}$ に引っ越すクエリが与えられる。
• $T_i=2$ の時 :　ビーバー $L_i$ ～ $R_i$ を招待してパーティーを開催する。

入力

$N\ K\ Q$
$C_{1}\ C_{2}\ \dots\ C_{N}$
$A_{1}\ A_{2}\ \dots\ A_{K}$
$E_{1}\ F_{1}$
$E_{2}\ F_{2}$
$\dots$
$E_{N-1}\ F_{N-1}$
$T_{1}\ \dots $
$\dots\ $
$T_{Q}\ \dots $

入力は全て整数
$1 \leq\ N,K,Q \leq\ 10^{5}$
$1 \leq\ C_{i} \leq\ 10^{9}$
$1 \leq\ A_{i} \leq\ N$
辺を順に辿っていくと頂点1にたどり着く
与えられるグラフは有向木である
$1 \leq T_{i} \leq 2$
$T_i=1$の時、クエリは以下の形式で与えられる。

$1\ X_i\ Y_i$     

$2\ L_i\ R_i$    

出力

パーティーが開かれる町の活気を出力し、最後に改行してください。

サンプル

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

2
4
1

3 4 5
86 91 20
3 3 1 2
3 1
2 1
1 3 1
2 2 3
1 3 2
2 2 2
2 3 3

86
86
91