LCA offline (Easy)

Изначально имеется дерево, состоящее только из корня (вершина с номером $1$). Требуется научиться отвечать на следующие запросы:

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

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

Вершины имеют номера от $1$ до $n$. В каждый момент времени у нас имеется одно дерево.

Входные данные

В первой строке содержится количество запросов $k$. Следующие $k$ строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит $1000$.

Выходные данные

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

Примеры