Cossack Vus and the Count#11076
Sign in

Cossack Vus and the Count

6 seconds
1,024 megabytes
Very hard

You are given a graph with vertices and 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 . 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 , , and (1 \leq n, q \leq 5 \cdot 10^5, 0 \leq g \leq 9).

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

  1. v_i, k_i (1 \leq v_i, k_i \leq n).

  2. v_i, u_i (1 \leq v_i, u_i \leq n).

  3. x_i (0 \leq x_i < i).

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Scoring

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

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

  3. ( points): n, q \leq 100.

  4. ( points): n, q \leq 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. ( points): n, q \leq 3 \cdot 10^5, no queries of the third type.

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

  7. ( points): n, q \leq 10^5.

  8. ( points): n, q \leq 3 \cdot 10^5.

  9. ( points): no additional constraints.