Description

As a great wizard, Frahc will one day find the ultimate forgotten great spell. At present, Frahc has been informed that the spell lies in a rooted binary tree, where the node with index $1$ is the root.

There is a spell written on each node. The spell on node $i$ is $w_i$. Obviously, since these spells have been written, they must not be the ultimate forgotten great spell. However, Frahc has seen through everything: the forgotten spell — just like its epithet — is the $\mathrm{mex}$ of the spells. The $\mathrm{mex}$ of a set of non-negative integers is defined as the minimal non-negative integer that is not in the set. Specifically, Frahc can explore one path in the tree, if so, he will learn the forgotten spell of the path.

Frahc believes the smaller the forgotten spell is, the more primitive the spell is, then the more likely the spell is the ultimate forgotten great spell. Also, Frahc likes longer paths. So he defines the priority of a path is the length of the path minus the forgotten spell of the path.

Frahc wants to find the maximum priority among all the paths, for each subtree. Since Frahc is a great wizard, not a great programmer, he leaves the problem to you.

Format

Input

The first line contains one integer $n\,(1\leq n\leq 3\times10^5)$, the size of the binary tree.

The second line contains $n$ numbers $w_1,w_2,\ldots,w_n\,(0\leq w_i<n)$.

The third line contains $n-1$ numbers $fa_2,fa_3,\ldots,fa_n(1\leq fa_i<i)$, where $fa_i$ is the parent node of node $i$.

Output

One line with $n$ numbers. The $i$-th number is the maximum path weight in node $i$'s subtree.

Samples

7
2 1 0 0 1 1 0
1 1 2 3 2 6

3 2 1 0 1 1 0