Рассмотрим корневое дерево. Изначально дерево состоит из одного лишь корня. На сыновьях каждой вершины определён порядок слева направо. Допустимые операции с деревом таковы: \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} выведите ответ на него в отдельной строке.