D. Дерево полураспада
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В последнее время Петя очень увлекся физикой. Анна Викторовна, его учительница, заметив Петину тягу к знаниям дала ему увлекательную физическую головоломку — дерево полураспада.

Дерево полураспада представляет собой полное двоичное дерево высоты h. Высота двоичного дерева — максимум среди расстояний (в ребрах) от корня дерева до его листьев. В процессе изучения, Петя добавляет в его вершины электроны, а также вызывает случайный распад дерева с помощью синхрофазотрона. Случайным распадом называется процесс при котором вдоль пути от корня к случайному листку удаляются все ребра. Вероятности выбора листьев равны между собой. Естественно, так как казенное имущество портить ученикам воспрещается, после каждого такого распада Петя возвращает все удаленные ребра на место.

Распавшись, дерево разлагается на компоненты связности. Зарядом такой компоненты называется суммарное количество электронов в вершинах, что принадлежат ей. Потенциалом разрушенного дерева называется максимальный заряд среди его компонент связности. Каждый раз вызывая случайный распад дерева, Петя предварительно хочет знать каково математическое ожидание потенциала дерева после его разрушения.

Входные данные

Первая строка будет содержать два целых числа h и q (1 ≤ h ≤ 30, 1 ≤ q ≤ 105). Далее идут q строк в каждой из которых будет запрос одного из двух типов:

  • add v e

    В вершину с номером v Петя добавляет e электронов (1 ≤ v ≤ 2h + 1 - 1, 0 ≤ e ≤ 104). v и e — целые числа.

    Вершины в дереве нумеруются следующим образом: корень имеет номер 1, потомки вершины x имеют номера 2x и 2x + 1.

  • decay

    Петя провоцирует распад дерева.

Выходные данные

Для каждого запроса decay следует вывести математическое ожидание потенциала дерева после его разрушения. Абсолютная или относительная погрешность ответа не должна превышать 10 - 4.

Примеры
Входные данные
1 4
add 1 3
add 2 10
add 3 11
decay
Выходные данные
13.50000000