Problem Statement

The JOI Kingdom has $N$ towns. Each town has a value called its liveliness. The liveliness of the $i$-th town is $C_i$.
These towns are connected by $N-1$ one-way roads. The $i$-th edge connects town $E_i$ and town $F_i$ in this direction.
The JOI Kingdom forms a rooted tree with vertex $1$ as the root, and all edges are directed toward the root.

Bitaro is a beaver living in the JOI Kingdom, and he loves parties. Bitaro's number is $1$.
He also has $K-1$ relatives numbered from $2$ to $K$, and all of them love parties too.
Initially, the $i$-th beaver lives in town $A_i$.

Bitaro and his relatives regularly hold parties so that the following conditions are satisfied.

• The beavers whose numbers satisfy $L \leq x \leq R$ are invited to the party.
• The venue must be a town reachable by all of the beavers above.
• Among the towns satisfying the condition above, the town with the maximum liveliness is chosen.
• After the party ends, all the beavers return home.

• When $T_i=1$: a query in which beaver $X_{i}$ moves to town $Y_{i}$ is given.
• When $T_i=2$: a party is held, inviting beavers $L_i$ through $R_i$.

Input

$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 $

All inputs are integers.
$1 \leq\ N,K,Q \leq\ 10^{5}$
$1 \leq\ C_{i} \leq\ 10^{9}$
$1 \leq\ A_{i} \leq\ N$
Following the edges in order leads to vertex 1.
The given graph is a directed tree.
$1 \leq T_{i} \leq 2$
When $T_i=1$, the query is given in the following format.

$1\ X_i\ Y_i$     

$2\ L_i\ R_i$    

Output

Output the liveliness of the town where the party is held, and print a newline at the end.

Sample

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