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

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

Всі номери вершин від 1 до \(𝑁\).

У кожний момент часу ми маємо одне дерево.

Формат вхідних даних

У першому рядку міститься число \(𝑘\) — кількість запитів.

Наступні \(k\) рядків містять самі запити.

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

Формат вихідних даних

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

Приклад вхідних даних

9
ADD 1 2
ADD 1 3
ADD 2 4
GET 1 3
GET 2 3
GET 3 4
ADD 2 5
GET 4 5
GET 5 5

Приклад вихідних даних

1
1
1
2
5