Дано граф з $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}