On an unweighted tree, there are ~N~ nodes and ~N - 1~ edges. The nodes are numbered from ~1~ to ~N~. All nodes ~i~ have a parent ~p_i~, except for the root node, for which ~p_i~ is ~0~. All nodes are able to reach the root by repeatedly going up the parent of the current node.

Initially, all nodes have a value of ~0~. Perform the following operation on each node ~i~:

Add ~x_i~ to the value of all nodes on the path from ~i~ to the root, including ~i~ and the root themselves.

Output the final values of all nodes.

Constraints

~1 \leq N \leq 1~ ~000~ ~000~

~1 \leq x_i \leq 2~ ~000~

Input Specification

The first line contains one number: ~N~.

The second line of input contains ~N~ numbers, the ~i~-th number is ~p_i~. If ~p_i~ is not ~0~, then node ~p_i~ is the parent of node ~i~. If ~p_i~ is ~0~, then the node is the root. It is guaranteed that there are no cycles and exactly one node is the root.

The third line of input contains ~N~ numbers, the ~i~-th number is ~x_i~. This means you must add ~x_i~ to the value of all nodes from ~i~ to the root, inclusive.

Output Specification

Output ~N~ lines, the ~i~-th line containing the value of node ~i~.

Sample Input

5
0 1 1 3 3
1 2 4 8 16

Sample Output

31
2
28
8
16

Explanation for Sample

The path to root for ~1~ is just ~1~. So, ~1~ should be incremented by ~x_1~ = ~1~.

The path to root for ~2~ is ~2 \to 1~. So, ~2~ and ~1~ should be incremented by ~x_2~ = ~2~.

The path to root for ~3~ is ~3 \to 1~. So, ~3~ and ~1~ should be incremented by ~x_3~ = ~4~.

The path to root for ~4~ is ~4 \to 3 \to 1~. So, ~4~, ~3~, and ~1~ should be incremented by ~x_4~ = ~8~.

The path to root for ~5~ is ~5 \to 3 \to 1~. So, ~5~, ~3~, and ~1~ should be incremented by ~x_5~ = ~16~.

Adding it all together the values at nodes ~1~, ~2~, ~3~, ~4~, and ~5~ are ~31~, ~2~, ~28~, ~8~, and ~16~, respectively.