A market's assets arose by branching. You are given a rooted tree with n nodes, numbered 1 to n; node 1 is the root. Node i carries an innovation e_i ~ N(mu_i, sigma_i^2), independent across nodes. The return of a node v is the sum of the innovations along the path from the root to v:

r_v = sum of e_u over all nodes u on the path 1 -> v

The leaves of the tree are the investable assets. Submit a long-only, fully invested portfolio over the leaves: one weight w_l per leaf, with w_l >= 0 and sum of w_l = 1. The lower the variance Var(sum of w_l * r_l over the leaves l), the better.

Input

The first line contains the integer n. If n >= 2, the second line contains n - 1 integers, the i-th of them being the parent of node i + 1; the parent of every node has a smaller number than the node itself. Each of the next n lines contains mu_i and sigma_i for node i, real numbers with at most 4 digits after the decimal point.

Output

One line per leaf, in increasing node number: the weight of that leaf.

Scoring

An output is rejected (score 0) unless it has exactly one weight per leaf, every weight is >= 0 (values down to -1e-9 are tolerated and treated as 0), and the weights sum to 1 within 1e-6. Accepted weights are renormalized to sum exactly 1, and the score of the case is

score = V_min / V

where V is the variance of your portfolio and V_min is the minimum variance achievable by any valid portfolio. The total score is the mean over the cases. A score of 1.0 on a case means your portfolio is optimal.

Constraints

1 <= n <= 50000

0.01 <= sigma_i <= 10

|mu_i| <= 1