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