One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn't search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn't have the key, and occured exactly one mistake. "That's not a problem!", thought Petya. "Why not count the expectation value of an element, which is found when I search for the key". The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to 0 or to 2. The nodes that have 0 children are called leaves and the nodes that have 2 children, are called inner. An inner node has the left child, that is the child whose key is less than the current node's key, and the right child, whose key is more than the current node's key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won't make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.
## Input
The first line contains an odd integer _n_ (3 ≤ _n_ < 105), which represents the number of tree nodes. Next _n_ lines contain node descriptions. The (_i_ + 1)\-th line contains two space-separated integers. The first number is the number of parent of the _i_\-st node and the second number is the key lying in the _i_\-th node. The next line contains an integer _k_ (1 ≤ _k_ ≤ 105), which represents the number of keys for which you should count the average value of search results containing one mistake. Next _k_ lines contain the actual keys, one key per line.
All node keys and all search keys are positive integers, not exceeding 109. All _n_ + _k_ keys are distinct.
All nodes are numbered from 1 to _n_. For the tree root "-1" (without the quote) will be given instead of the parent's node number. It is guaranteed that the correct binary search tree is given. For each node except for the root, it could be determined according to its key whether it is the left child or the right one.
## Output
Print _k_ real numbers which are the expectations of answers for the keys specified in the input. The answer should differ from the correct one with the measure of absolute or relative error not exceeding 10 - 9.
[samples]
## Note
In the first sample the search of key 1 with one error results in two paths in the trees: (1, 2, 5) and (1, 3, 6), in parentheses are listed numbers of nodes from the root to a leaf. The keys in the leaves of those paths are equal to 6 and 10 correspondingly, that's why the answer is equal to 8.
一天晚上，经过辛苦的工作后，Petya 做了一个噩梦。梦中出现了一棵二叉搜索树。但真正让 Petya 恐惧的并不是这棵树本身，而是他无法在这棵树中搜索元素。他多次尝试选择一个键值并在树中查找，但每次都走错了路径。Petya 苦苦思索了很久，反复尝试不同的键值，但结果始终不佳。就在他即将绝望之际，他突然顿悟：每次他查找时，树中都不包含该键值，且恰好发生了一次错误。
“这没问题！”Petya 想道，“为什么不计算一下，当我搜索某个键值时，最终找到的元素的期望值呢？”就在他准备开始计算时，Petya 突然醒了。
因此，你被给定一棵#cf_span(class=[tex-font-style-underline], body=[binary search tree])，树中每个节点包含一个数字，称为#cf_span(class=[tex-font-style-underline], body=[node key])。每个节点的子节点数量要么是#cf_span[0]，要么是#cf_span[2]。拥有#cf_span[0]个子节点的节点称为#cf_span(class=[tex-font-style-underline], body=[leaves])，拥有#cf_span[2]个子节点的节点称为#cf_span(class=[tex-font-style-underline], body=[inner])。一个内节点有一个#cf_span(class=[tex-font-style-underline], body=[left child])（其键值小于当前节点的键值）和一个#cf_span(class=[tex-font-style-underline], body=[right child])（其键值大于当前节点的键值）。此外，任意节点的键值严格大于其左子树中所有节点的键值，且严格小于其右子树中所有节点的键值。
你还被给定一组#cf_span(class=[tex-font-style-underline], body=[search keys])，所有键值互不相同，且与树中节点的键值均不同。对于集合中的每个键值，都会在树中进行一次搜索。搜索过程如下：初始时位于树的根节点，如果当前节点的键值大于搜索键值，则移动到该节点的左子节点；否则移动到右子节点，并重复此过程。由于保证搜索键值不在树中，搜索总会终止于某个叶子节点，该叶子节点中的键值被声明为#cf_span(class=[tex-font-style-underline], body=[search result])。
可以确定的是，在搜索过程中恰好发生了一次比较错误，即有一次走错了方向，但之后不会再犯任何错误。所有可能的错误出现的概率相等，即我们必须考虑所有恰好发生一次错误的搜索路径。你的任务是，对于每个搜索键值，计算在恰好发生一次错误的条件下，搜索结果的期望值（平均值）。也就是说，对于给定键值的所有恰好包含一次错误的路径，你需要计算这些路径叶子节点中键值的平均值。
第一行包含一个奇数#cf_span[n]（#cf_span[3 ≤ n < 105]），表示树中节点的数量。接下来的#cf_span[n]行包含节点描述。第#cf_span[(i + 1)]行包含两个用空格分隔的整数：第一个数是第#cf_span[i]个节点的父节点编号，第二个数是第#cf_span[i]个节点中的键值。下一行包含一个整数#cf_span[k]（#cf_span[1 ≤ k ≤ 105]），表示需要计算包含一次错误的搜索结果平均值的键值数量。接下来的#cf_span[k]行每行包含一个实际的键值。
所有节点键值和所有搜索键值均为不超过#cf_span[109]的正整数。所有#cf_span[n + k]个键值互不相同。
所有节点编号从#cf_span[1]到#cf_span[n]。对于树根，父节点编号将用“-1”（不含引号）表示。保证给出的是一棵正确的二叉搜索树。对于除根节点外的每个节点，可以根据其键值判断它是左子节点还是右子节点。
请输出#cf_span[k]个实数，分别表示输入中指定键值的期望答案。答案与正确答案的绝对误差或相对误差不得超过#cf_span[10 - 9]。
在第一个样例中，键值1在发生一次错误时的搜索路径有两条：(1, 2, 5) 和 (1, 3, 6)，括号内列出的是从根到叶子的节点编号。这两条路径叶子节点的键值分别为6和10，因此答案为8。
## Input
第一行包含一个奇数#cf_span[n]（#cf_span[3 ≤ n < 105]），表示树中节点的数量。接下来的#cf_span[n]行包含节点描述。第#cf_span[(i + 1)]行包含两个用空格分隔的整数：第一个数是第#cf_span[i]个节点的父节点编号，第二个数是第#cf_span[i]个节点中的键值。下一行包含一个整数#cf_span[k]（#cf_span[1 ≤ k ≤ 105]），表示需要计算包含一次错误的搜索结果平均值的键值数量。接下来的#cf_span[k]行每行包含一个实际的键值。所有节点键值和所有搜索键值均为不超过#cf_span[109]的正整数。所有#cf_span[n + k]个键值互不相同。所有节点编号从#cf_span[1]到#cf_span[n]。对于树根，父节点编号将用“-1”（不含引号）表示。保证给出的是一棵正确的二叉搜索树。对于除根节点外的每个节点，可以根据其键值判断它是左子节点还是右子节点。
## Output
请输出#cf_span[k]个实数，分别表示输入中指定键值的期望答案。答案与正确答案的绝对误差或相对误差不得超过#cf_span[10 - 9]。
[samples]
## Note
在第一个样例中，键值1在发生一次错误时的搜索路径有两条：(1, 2, 5) 和 (1, 3, 6)，括号内列出的是从根到叶子的节点编号。这两条路径叶子节点的键值分别为6和10，因此答案为8。
**Definitions**
Let $ T $ be a binary search tree with $ n $ nodes, where each node $ i $ has a unique key $ v_i \in \mathbb{Z}^+ $, and parent pointer $ p_i \in \{0, 1, \dots, n\} $ (with $ p_i = -1 $ for root).
Let $ L \subseteq \{1, \dots, n\} $ be the set of leaf nodes.
Let $ \mathcal{P}(k) $ be the set of all paths from the root to a leaf in $ T $ that result from a search for key $ k $ with exactly one comparison error (and no subsequent errors), where each path corresponds to a unique leaf $ \ell \in L $.
**Constraints**
1. $ 3 \leq n < 10^5 $, odd.
2. Each node has 0 or 2 children.
3. For any inner node with key $ v $, all keys in left subtree $ < v $, all keys in right subtree $ > v $.
4. All node keys and search keys are distinct positive integers $ \leq 10^9 $.
5. For each search key $ k $, $ k \notin \{v_1, \dots, v_n\} $.
6. Exactly one comparison error occurs during search; all such paths with one error are equally probable.
**Objective**
For each search key $ k $, compute the expected value of the leaf key reached under exactly one comparison error:
$$
\mathbb{E}[k] = \frac{1}{|\mathcal{P}(k)|} \sum_{\ell \in \mathcal{P}(k)} v_\ell
$$
where $ \mathcal{P}(k) $ is the set of leaves reachable via search paths for $ k $ with exactly one wrong comparison.