Казак Вус и граф

Дан граф с $n$ вершинами и $q$ запросов трех типов:

1. Найдите $k_i$-ую наименьшую по номеру вершину в компоненте связности вершины $v_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$ баллов): без дополнительных ограничений.