\begin{problem}{Козак Вус та граф}{standard input}{standard output}{6 seconds}{1024 megabytes}

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

\begin{enumerate}
\item У компоненті вершини $v_i$ потрібно знайти номер $k_i$-ої найменшої за номером вершини. Якщо такої немає, то потрібно повернути $-1$. Компонента вершини $v_i$ --- це множина усіх вершин, до яких можна дістатися з вершини $v_i$ по ребрах.
\item Додати до графа ребро, що з'єднує вершини $u_i$ та $v_i$.
\item Повернутися до стану, який був після виконання $x_i$ операцій.
\end{enumerate}

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

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

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

\begin{enumerate}
\item $v_i$, $k_i$ ($1 \leq v_i, k_i \leq n$).
\item $v_i$, $u_i$ ($1 \leq v_i, u_i \leq n$).
\item $x_i$ ($0 \leq x_i < i$).
\end{enumerate}

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

\Scoring
\begin{enumerate}
\item ($6$ балів): $n, q \leq 100$; немає операцій другого та третього типів.
\item ($7$ балів): $n, q \leq 100$; немає операцій третього типу.
\item ($4$ бали): $n, q \leq 100$.
\item ($9$ балів): $n, q \leq 3 \cdot 10^5$; гарантується, що в операціях другого типу $|v_i-u_i|=1$; немає запитів третього типу.
\item ($8$ балів): $n, q \leq 3 \cdot 10^5$, немає запитів третього типу.
\item ($10$ балів): $n, q \leq 3 \cdot 10^5$; гарантується, що в операціях другого типу $|v_i-u_i|=1$.
\item ($19$ балів): $n, q \leq 10^5$.
\item ($17$ балів): $n, q \leq 3 \cdot 10^5$.
\item ($20$ балів): без додаткових обмежень.
\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\exmpfile{example.03}{example.03.a}%
\exmpfile{example.04}{example.04.a}%
\end{example}

\end{problem}

