In the world of OI, there is a legendary figure known to everyone, a master of competitive programming whose skills are unparalleled: Hu Ce, often called "Master Hu, the One-Second Problem Solver."
Hu Ce recently received a magical sapling from a mysterious man who calls himself Little O.
This is a rooted tree with $n$ nodes, labeled $1, \dots, n$, where node $1$ is the root.
Each node in this rooted tree has a weight, where the weight of node $i$ is $a_i$. The values $a_1, \dots, a_n$ form a permutation of $0 \sim n-1$, and $a_1=0$.
Master Hu loves monkeys very much and plans to keep $n$ monkeys on this tree. Initially, exactly one monkey is placed on each node. The monkeys are very active; every second, each monkey at node $i$ attempts to jump to its parent node. It succeeds with probability $p(i)$; otherwise, the jump fails, and it lands on a node within the subtree of $i$ (including node $i$) with uniform probability.
Since the root has no parent, $p(1)=0$. For $2\leq i\leq n$, $p(i)=\frac{a_i}{n}$.
At each second $i$, Hu Ce observes and records the proportion $g_i$ of the $n$ monkeys that successfully jumped to their parent nodes. Hu Ce defines the happiness index of these monkeys as the average value of $g_0, \dots, g_T$. To ensure accuracy, $T$ is a very, very large value, specifically $(n+1)^{99999^{99999^{99999}}}$.
To maximize the expected happiness index of the monkeys, Hu Ce bought a bag of fertilizer called "Golden Kela" from the mysterious man. If $x$ grams of Golden Kela are added to the rooted tree, the weight of each node $i$ changes to $(a_i+x) \bmod n$. Since Hu Ce is wealthy and can do as he pleases, $x$ can be any non-negative integer.
Please tell Hu Ce how many grams of Golden Kela he should add to maximize the expected happiness index of the monkeys.
Input
The first line contains a positive integer $n$.
The second line contains $n$ space-separated non-negative integers, where the $i$-th integer is the parent node index $f_i$ of node $i$ ($f_1=0$, and for $i>1$, $1\leq f_i < i$).
The third line contains $n$ space-separated non-negative integers, representing a permutation of $0 \sim n-1$, where the $i$-th integer is $a_i$.
Output
A single real number representing the maximum expected happiness index when the optimal amount of Golden Kela is added.
Your answer is considered correct if the absolute or relative error between your answer and the standard answer does not exceed $10^{-9}$.
Examples
Input 1
3 0 1 1 0 1 2
Output 1
0.266666667
Input 2
See sample data download.
Output 2
See sample data download.
Constraints
For 10% of the data: $n = 2$.
For 20% of the data: $n\leq 5$.
For 30% of the data: $n\leq 100$.
For 50% of the data: $n\leq 2000$.
For 70% of the data: $n\leq 100000$.
For 100% of the data: $2\leq n\leq 500000$.
The data is guaranteed to have a certain gradient.
The data is randomly generated. That is, the parent of node $i$ is chosen uniformly at random from $1 \sim i-1$, and $a_1 \dots a_n$ is a random permutation of $0 \sim n-1$.