問題文
正整数$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がすでに同じ集合に属しているので何もしなくてよい