Cossack Vus and the Count

You are given a graph with $n$ vertices and $q$ queries of three types:

1. For a given vertex $v_i$, find the $k_i$-th smallest vertex number in its connected component. If such a vertex does not exist, return $-1$. The connected component of $v_i$ includes all vertices reachable from $v_i$ via edges.

2. Add an edge between vertices $u_i$ and $v_i$.

3. Revert the graph to its state after the $x_i$-th operation.

Your task is to provide answers for all queries of the first type.

Input

The first line contains three integers $n$, $q$, and $g$ ($1\le n,q\le 5\cdot 10^5$, $0\le g\le 9$).

Each of the following lines contains a query in one of the following formats:

1. $v_i$, $k_i$ ($1\le v_i,k_i\le n$).

2. $v_i$, $u_i$ ($1\le v_i,u_i\le n$).

3. $x_i$ ($0\le x_i<i$).

Output

For each query of the first type, output the result.

Examples

Scoring

1. ($6$ points): $n,q\le 100$; no queries of the second and third types.

2. ($7$ points): $n,q\le 100$; no queries of the third type.

3. ($4$ points): $n,q\le 100$.

4. ($9$ points): $n,q\le 3\cdot 10^5$; for queries of the second type, it is guaranteed that $|v_i-u_i|=1$; no queries of the third type.

5. ($8$ points): $n,q\le 3\cdot 10^5$, no queries of the third type.

6. ($10$ points): $n,q\le 3\cdot 10^5$; for queries of the second type, it is guaranteed that $|v_i-u_i|=1$.

7. ($19$ points): $n,q\le 10^5$.

8. ($17$ points): $n,q\le 3\cdot 10^5$.

9. ($20$ points): no additional constraints.