Лимак — это маленький медвежонок гризли. Однажды он нападёт на страну оленей, но пока что он занимается уничтожением деревьев в компьютерной ролевой игре. Лимак начинает с дерева, состоящего из одной вершины. Эта вершина имеет индекс 1 и является корнем дерева.
Время от времени игра выбирает некоторое поддерево, и Лимак атакует его. Когда Лимак атакует поддерево, он разрушает каждое его ребро независимо с вероятностью 
. Штрафом Лимака после атаки на поддерево является целое число, равное высоте поддерева после атаки. Высотой поддерева называется самый длинный простой путь, начинающийся в корне поддерева и заканчивающийся в какой-нибудь вершине поддерева.
Вам требуется обрабатывать запросы двух типов.
- 1 v обозначает запрос первого типа. В дерево добавляется новая вершина, и её родителем является вершина v. Вершина получает минимальный свободный индекс (таким образом, вершины получают номера 2, 3, ...).
- 2 v обозначает запрос второго типа. Предположим, Лимак атакует поддерево вершины v. Чему в таком случае равно математическое ожидание штрафа, который он получит?
В запросах второго типа только предполагается, что Лимак атакует поддерево, но на самом деле никакие рёбра не разрушаются, и этот запрос никак не влияет на последующие.
Выходные данные
Для каждого запроса второго типа выведите одно вещественное число — математическое ожидание штрафа Лимака после атаки на соответствующее поддерево. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
Примечание
На рисунке ниже представлен первый пример. Красными кружочками обозначены запросы второго типа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 1
1 1
2 1
1 2
1 3
2 2
2 1
|
0.7500000000
0.5000000000
1.1875000000
|
|
2
|
8
2 1
1 1
1 2
1 3
1 4
2 1
1 4
2 1
|
0.0000000000
0.9375000000
0.9687500000
|