A company newly founded by Luna. This company, whenever assigned a task, breaks the task down into smaller tasks. One task will be split into many smaller tasks, each with its own completion time. Specifically, there are a total of ~n~ tasks, each task is broken down from exactly one task, and one task can be divided into many smaller tasks (except for task 1). The ~i^{th}~ task has a completion time of ~t_i~ . A task is considered completed when both it and the tasks it was divided into are finished.

Calculate the completion time for all tasks.

Input

The first line contains the integer ~n~ ~(1 ≤ n ≤ 2 · 10^5)~, which is the number of tasks.

The second line contains ~n - 1~ values ~p_2, p_3,... , p_n~, where each ~p_i~ indicates that the ~i^{th}~ task is derived from task ~p_i~ ~(1 ≤ p ≤ n)~.

The third line contains ~n~ values ~t_1, t_2,... , t_n~ ~(t ≤ 10^9)~, which are the completion times for the ~i^{th}~ task.

Output

A single line containing ~n~ values, which are the completion times for the ~i^{th}~ task.

Sample Input 1

5
1 1 2 2
1 1 1 1 1

Sample Ouput 1

5 3 1 1 1