Naganohara Yoimiya has given you a rooted tree with $n$ nodes, where node $1$ is the root and each node $i$ has a weight $w_i$.

For each node $u$, you need to find a non-empty connected subgraph (a subtree in the context of the rooted structure) that includes $u$ as its root, such that the average of the weights of all nodes in this connected subgraph is maximized.

Output this maximum average for each node $u$.

Input

The first line contains a positive integer $n$.

The next line contains $n-1$ positive integers $p_2, p_3, \dots, p_n$, where $p_i$ is the parent of node $i$. It is guaranteed that $p_i < i$.

The next line contains $n$ positive integers $w_1, w_2, \dots, w_n$.

Output

Output $n$ lines, where the $i$-th line contains a real number representing the maximum average weight of a connected subgraph rooted at node $i$.

Your answer will be considered correct if the relative or absolute error does not exceed $10^{-6}$.

Constraints

For all test cases, $1 \le n \le 2 \times 10^5$, $1 \le w_i \le 10^9$.

• Subtask 1 ($10$ points): $1 \le n \le 2000$.
• Subtask 2 ($10$ points): $p_i = \lfloor i/2 \rfloor$.
• Subtask 3 ($40$ points): $1 \le n \le 50000$.
• Subtask 4 ($40$ points): No additional constraints.

Examples

Input 1

6
1 2 2 1 4
3 1 5 6 6 7

Output 1

4.6666666667
4.7500000000
5.0000000000
6.5000000000
6.0000000000
7.0000000000