1232 - Corner Kth ⇔ Corner Case

問題文

正整数$K$と、$N$個の正整数 $A_1, A_2,,,A_N$ があります。

最初、$A_1, A_2,,,A_N$ はそれぞれが独立した集合に属しています。

次の2種類のクエリを処理しなさい。クエリは全部で$M$個与えられます。

• unite$(X, Y)$: $X$と$Y$が属する集合を併合する。ただし$X$と$Y$がすでに同じ集合に属している場合は何もしない
• findKth$(X)$: $X$が属する集合のうち$K$番目に小さい数を答える。ただし集合の要素数が$K$に満たない場合 $-1$ を出力する。

入力

以下の形式で与えられる。

最初の1行に$N, M, K$が与えられ、次の1行に$A_i (1 \leq i \leq N)$が空白区切りで与えられる。

続く$M$行にクエリが与えれる。

N M K
A1 A2 ... AN
query1
query2
:
queryM

queryは、

1 X Y

のとき、unite$(X, Y)$を表し、

2 X

のとき、findKth$(X)$を表す。

出力

各findKthクエリについて答えを1行に出力せよ。

制約

• $1 \leq N, M \leq 10^5$
• $1 \leq K \leq N$
• $1 \leq A_i \leq 10^9 (1 \leq i \leq N)$
• $A_i \neq A_j (i \neq j)$
• $X, Y \in A$
• findKthクエリは必ず1度以上与えられる。

入出力例

入力1

10 10 3
1 2 3 4 5 6 7 8 9 10
1 1 3
1 1 4
1 1 5
1 2 6
1 2 7
1 2 8
2 1
2 2
2 10
2 6

出力1

4
7
-1
7

このサンプルでは最初の6個のクエリを処理すると $\{1, 3, 4, 5\}, \{2, 6, 7, 8\}, \{9\}, \{10\}$ にまとめられる。

ここで、1が属する集合で3番目に小さいのは4、 2と6が属する集合で3番目に小さいのは7である。10が属する集合は要素数が3に満たないため-1を出力する。

入力2

6 5 2
1 2 3 5 8 13
2 1
1 1 13
1 1 2
1 2 13
2 1

出力2

-1
2

クエリ4の時点で2と13がすでに同じ集合に属しているので何もしなくてよい