Спочатку є дерево, яке містить лише корінь (вершина з номером ). Потрібно навчитись відповідати на наступні запити:
ADD — підвісити вершину за вершину (гарантується, що вершина вже існує).
GET — повернути LCA вершин та .
Вершини пронумеровані від до . У кожен момент часу у нас є одне дерево.
У першому рядку міститься число — кількість запитів. Наступні рядків містять самі запити. Гарантується, що число запитів кожного з типів не перевищує .
Для кожного запиту типу GET виведіть в окремий рядок одне ціле число — відповідь на відповідний запит.