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