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

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

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

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

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

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

Вхідні дані

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

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

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$).

Вихідні дані

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

Приклади

Оцінювання

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

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

3. ($4$ балів): $n,q\le 100$.

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

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

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

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

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

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