C. Петя и дерево
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Однажды после тяжелого рабочего дня Пете приснился страшный сон. И было в том сне большое бинарное дерево поиска. Но не дерево пугало Петю, а то, что не получалось у Пети искать в этом дереве элементы. Сколько ни пробовал Петя загадывать ключ и искать его в дереве, каждый раз приходил куда-то не туда. Долго мучился Петя, много загадывал ключей, и все одно и то же. Отчание стало охватывать Петю, как вдруг на него снизошло озарение: каждый раз, когда он искал ключ, этого ключа не было в дереве, и при этом случалась ровно одна ошибка. "Не беда!" — подумал Петя, — "А посчитаю-ка я матожидание значения элемента, который находится при поиске данного ключа." Только он собрался это сделать, как, вдруг, проснулся.

Итак, вам дано бинарное дерево поиска, то есть дерево, у которого в каждой вершине записано некоторое число, называемое ключом вершины. Количество сыновей у каждой вершины дерева равно либо 0, либо 2. Вершины, имеющие 0 сыновей, называются листьями, а вершины, имеющие 2 сыновей, называются внутренними. У внутренней вершины есть левый сын, то есть сын, у которого ключ меньше ключа текущей вершины, и правый сын, у которого ключ больше ключа текущей вершины. Потомками некоторой вершины называются все вершины, достижимые из нее. То есть это непосредственные сыновья вершины, сыновья сыновей, и так далее. Левые потомки вершины — потомки ее левого сына. Аналогично, правые потомки вершины — потомки ее правого сына. По свойству дерева поиска, ключ любой вершины строго больше всех ключей левых потомков вершины и строго меньше всех ключей правых потомков вершины.

Так же вам задан набор ключей поиска, все из которых различны и отличаются от ключей вершин, имеющихся в дереве. Для каждого ключа из набора выполняется его поиск в дереве. Поиск устроен следующим образом: изначально мы находимся в корне дерева, если ключ текущей вершины больше нашего ключа поиска, то мы переходим в левого сына вершины, иначе переходим в правого сына вершины, и процесс повторяется. Так как ключ поиска гарантированно не содержится в дереве, поиск всегда будет останавливаться в листьях дерева. Ключ, лежащий в листе, объявляется результатом поиска.

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

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

В первой строке задано нечетное целое число n (3 ≤ n < 105) — количество вершин в дереве. В следущих n строках заданы описания вершин. На (i + 1)-ой строке записано два целых числа, разделенных пробелами. Первое число — это номер родителя i-ой вершины, второе — это ключ, лежащий в i-ой вершине. В следующей строке записано целое число k (1 ≤ k ≤ 105) — количество ключей, для которых надо посчитать среднее значение результатов поиска с одной ошибкой. В следующих k строках записаны сами ключи, по одному в каждой строке.

Все ключи вершин и все ключи поиска — это целые положительные числа, не превосходящие 109. Все n + k ключей различны.

Все вершины нумеруются от 1 до n. Для корня дерева вместо номера вершины родителя будет задано число «-1» (без кавычек). Гарантируется, что задано корректное бинарное дерево поиска. Для каждой вершины, кроме корня, согласно её ключу может быть установлено, является она левым или правым сыном.

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

Выведите k действительных чисел, являющихся матожиданиями ответов для ключей, заданных во входе. Ответ должен отличаться от правильного с относительной или абсолютной погрешностью не более 10 - 9.

Примеры
Входные данные
7
-1 8
1 4
1 12
2 2
2 6
3 10
3 14
1
1
Выходные данные
8.0000000000
Входные данные
3
-1 5
1 3
1 7
6
1
2
4
6
8
9
Выходные данные
7.0000000000
7.0000000000
7.0000000000
3.0000000000
3.0000000000
3.0000000000
Примечание

В первом сэмпле поиск ключа 1 с одной ошибкой порождает в дереве два пути: (1, 2, 5) и (1, 3, 6), в скобках перечислены номера вершин от корня к листу. Ключи в листьях этих путей равны 6 и 10 соответственно, поэтому ответ равен 8.