Дерево
Розглянемо кореневе дерево. Спочатку дерево складається лише з одного кореня. Для синів кожної вершини визначено порядок зліва направо. Допустимі операції з деревом такі:
Додати у дерево лист.
Видалити з дерева лист.
Знайти кількість вершин на шляху між двома листками.
Знайти кількість "під шляхом" між двома листками.
Множина вершин, яка лежить "під шляхом" між листками u та v, визначається наступним чином. Розглянемо шлях u=w_0-w_1-...-w_k=v між ними. Виділимо у ньому ту вершину w_c, у якій обидва ребра шляху йдуть до її синів. Нехай для визначенності ліве з цих ребер наближаєт нас до вершини u, а праве - до вершини v. Тоді таким, що лежать "під шляхом" оголошуються наступні вершини:
Усі сини w_c, які лежать між w_{c-1} та w_{c+1}, а також усі вершини їхніх піддерев;
Для i = 1, 2, ..., c-1 - усі сини w_i, які лежать правіш сина w_{i-1}, а також усі вершини їхніх піддерев;
Для i = c+1, c+2, ..., k-1 - усі сини w_i, які лежать лівіше сина w_{i+1}, а також усі вершини їхніх піддерев.
Напишіть програму, яка за послідовністю запитів перебудовує дерево згідно запитів на додавання та видалення вершин, а також обчислює відповіді на запити про кількість вершин на шляху і "під шляхом".
Вхідні дані
У першому рядку вхідного файлу міститься одне ціле число n - кількість запитів (0 ≤ n ≤ 300000). Кожен з наступних n рядків описує один запит. Можливі види запитів такі:
l x - додати новий лист як самого лівого сина вершини x.
r x - додати новий лист як самого правого сина вершини x.
a x y - додати новий лист як сина вершини x, який знаходиться безпосередньо праворуч від вершини y; усі сини x, які знаходився до цього праворуч від y, після додавання опиняються правіше нової вершини; гарантується, що y є сином x.
d x - видалити вершину x. Гарантується, що у цей момент вершина x не видалена і є листом.
p x y - знайти кількість вершин на шляху між x та y, включаючи самі ці вершини; гарантиується, що x та y є листами.
q x y - знайти кількість вершин "під шляхом" між x та y, включаючи самі ці вершини; гарантується, що x та y є листками.
Вершини, що додаються, нумеруються з одиниці у тому порядку, у якому вони додаються у запитах. Корінь дерева має номер 0 і листом ні у який момент часу не вважається.
Вихідні дані
Виконуючи запити по порядку, на кожен запит виду p або q виведіть відповідь на нього у окремому рядку.