Нові амбари

Фермер Джон помітив, що його корови часто сваряться, якщо вони занадто близько одна до одної, тому він хоче відкрити серію нових амбарів, щоб розмістити їх рівномірно.

Кожного разу, коли ФД будує новий амбар, він з'єднує його не більш ніж однією двонаправленою дорогою з вже існуючим амбаром. Щоб впевнитися, що корови розташовані на достатньо великій відстані одна від одної, іноді він хоче визначити відстань від певного амбару до найвіддаленішого амбара, досяжного з нього (відстань між двома амбарами - це кількість доріжок, які потрібно пройти, щоб перейти з одного амбару в інший).

ФД надасть в сумі q запитів, кожен з яких має форму "побудувати" або "відстань". Для запиту "побудувати" ФД будує амбар та з'єднує його з найбільше одним побудованим амбаром. Для запиту "відстань" ФД запитує у вас відстань від певного амбару до найвіддаленішого амбара, досяжного з нього за допомогою послідовності доріжок. Гарантується, що запитуваний амбар вже побудований. Будь ласка, допоможіть ФД відповісти на всі ці запити.

Вхідні дані

У першому рядку міститься ціле число q (1 ≤ q ≤ 10^5). Кожен з наступних q рядків містить запит. Кожен запит має форму "B p" або "Q k", що вказує вам побудувати або підрахувати найвіддаленішу відстань від амбару p або k відповідно. Якщо p = −1, то новий амбар не буде з'єднаний з жодним іншим амбаром з вже побудованих. Інакше p - це номер амбару, який вже побудований. Амбари нумеруються з 1, отже, перший побудований амбар матиме номер 1, другий - 2, і так далі.

Вихідні дані

Виведіть по одному рядку для кожного запиту "відстань". Зверніть увагу, що амбар, який не з'єднаний з іншими амбарами, має найвіддаленішу відстань 0.

Приклад

Приклад введення відповідає такій мережі амбарів:

  (1) 
    \   
     (2)---(4)
    /
  (3)

У запиті 1 ми будуємо амбар номер 1. У запиті 2 ми запитуємо відстань від 1 до найвіддаленішого з'єднаного амбару. Оскільки амбар 1 не з'єднаний з іншими амбарами, відповідь 0. У запиті 3 ми будуємо амбар номер 2 і з'єднуємо його з амбаром 1. У запиті 4 ми будуємо амбар номер 3 і з'єднуємо його з амбаром 2. У запиті 5 ми запитуємо відстань від 3 до найвіддаленішого з'єднаного амбару. У цьому випадку найвіддаленішим є амбар 1, який віддалений на 2 одиниці. У запиті 6 ми будуємо амбар номер 4 і з'єднуємо його з амбаром 2. У запиті 7 ми запитуємо відстань від 2 до найвіддаленішого з'єднаного амбару. Всі три амбари 1, 3, 4 знаходяться на відстані 1, тому відповідь 1.

Приклади