LCA offline

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

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

• GET a b - вернуть LCA вершин a и b.

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

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

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

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

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

Примеры