LCA offline

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади