Козак Вус та граф#101

Козак Вус та граф

6 seconds
1,024 megabytes
Very hard

Дано граф з вершин. Також дано запитів трьох типів:

  1. У компоненті вершини v_i потрібно знайти номер k_i-ої найменшої за номером вершини. Якщо такої немає, то потрібно повернути . Компонента вершини v_i — це множина усіх вершин, до яких можна дістатися з вершини v_i по ребрах.

  2. Додати до графа ребро, що з'єднує вершини u_i та v_i.

  3. Повернутися до стану, який був після виконання x_i операцій.

Знайдіть відповіді на всі запити першого типу.

Input

Перший рядок містить три цілі числа , , (1 \leq n, q \leq 5 \cdot 10^5, 0 \leq g \leq 9).

Кожен з наступних рядків описує запит.

  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

Для кожного запиту першого типу виведіть відповідь на запит.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Scoring

  1. ( балів): n, q \leq 100; немає операцій другого та третього типів.

  2. ( балів): n, q \leq 100; немає операцій третього типу.

  3. ( балів): n, q \leq 100.

  4. ( балів): n, q \leq 3 \cdot 10^5; гарантується, що в операціях другого типу |v_i-u_i|=1; немає запитів третього типу.

  5. ( балів): n, q \leq 3 \cdot 10^5, немає запитів третього типу.

  6. ( балів): n, q \leq 3 \cdot 10^5; гарантується, що в операціях другого типу |v_i-u_i|=1.

  7. ( балів): n, q \leq 10^5.

  8. ( балів): n, q \leq 3 \cdot 10^5.

  9. ( балів): без додаткових обмежень.