As a way to increase collaboration between employees of different ranks, Manly Software Solutions decided to create friendships inside the company.
The company has $n$ employees, each having an $id$ number from $1$ to $n$, every employee in the company has a manager, except of the CEO who has an $id$ of $1$, so the structure of the employees looks like a tree, also every employee has a value $p_i$ representing his personality.
The company wants every employee to make a friendship with a junior of his that is exactly $4$ ranks below him(meaning he is the manager of the manager of the manager of the manager of that employee).
Since employees are busy working, they want you to find for every employee the best candidate for creating a friendship with, the best candidate is the employee with the closest personality value(that is the difference between their personality values is minimum), if there are multiple such employees then the one with the lowest $id$ value among them is considered the best candidate.
Given the tree structure of the employees and their personality values, print for each employee the $id$ of his best candidate for friendship making, or state that no such candidate exists.
The first line contains a single integer $n$($1 \le n \le 2 \cdot 10^5$), the number of employees in the company.
The second line contains $n-1$ integers $m_2, m_3, ..., m_n$($1 \le m_i < i$), the manager of the $i$th employee.
The third line contains $n$ integers $p_1, p_2, ..., p_n$($1 \le p_i \le 10^9$), the personality of the $i$th employee.
Print a single line containing $n$ integers, the $i$th of them being the $id$ of the best candidate for the $i$th employee, or $0$ if there is no such candidate.
In the first example, the CEO($id=1$) has two juniors that are exactly four ranks lower than him, employee $5$ and $9$, the difference of personality with employee $5$ is $|3 - 6| = 3$, and with employee $9$ is $|3 - 10| = 7$, so employee $5$ is his best candidate.
The second employee has two juniors, employee $6$ and $10$, $10$ is the best candidate.
None of the other employees have a junior that is exactly $4$ ranks lower than them.
10 1 2 3 4 5 2 7 8 9 3 20 5 3 6 13 9 3 10 15
5 10 0 0 0 0 0 0 0 0