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

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

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

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