LCA offline (Easy)

Спочатку є дерево, яке містить лише корінь (вершина з номером $1$). Потрібно навчитись відповідати на наступні запити:

• ADD $ab$ — підвісити вершину $b$ за вершину $a$ (гарантується, що вершина $a$ вже існує).

• GET $ab$ — повернути LCA вершин $a$ та $b$.

Вершини пронумеровані від $1$ до $n$. У кожен момент часу у нас є одне дерево.

Вхідні дані

У першому рядку міститься число $k$ — кількість запитів. Наступні $k$ рядків містять самі запити. Гарантується, що число запитів кожного з типів не перевищує $1000$.

Вихідні дані

Для кожного запиту типу GET виведіть в окремий рядок одне ціле число — відповідь на відповідний запит.

Приклади