Республиканская олимпиада по информатике 2017 года за 10 класс | Казахстанские олимпиады

Задача F. Обещаю, последняя задача с деревом :)

Дано подвешенное бинарное дерево изначально состоящее из одной вершины с номером 1. Вам предстоит обработать $M$ запросов следующих типов :

Формат входного файла

Первая строка входного файла содержит целое число $M$ $(1 \leq M \leq 2 \cdot 10^5)$ — количество запросов.

В последующих $M$ строках содержится описания операций. Каждая операция описывается строкой $Op$ $V$, где $Op$ — тип операции ($Grow$ либо $Sum$), а $V$ — номер вершины для которой она выполняется.

Формат выходного файла

Для каждой операции типа $Sum$ в выходной файл на отдельной строке необходимо вывести соответствующую сумму. Выводите операции в том же порядке в котором они идут во входном файле.

Примеры

Вход

5
Grow 1
Grow 1
Grow 2
Sum 1
Sum 4

Выход

66
21