Given a tree with $n$ nodes, each node $i$ has a weight $a_i$.

For each node $x$, the answer is the maximum XOR sum $a_i \oplus a_j$ of two nodes $i$ and $j$ (which can be the same) chosen from all nodes outside the subtree rooted at $x$. If it is impossible to choose two such nodes, the answer for $x$ is $0$.

Input

The first line contains an integer $n$.

The next line contains $n-1$ integers, where the $i$-th integer represents the parent $j$ of node $i+1$, with the guarantee that $j < i+1$.

The next line contains $n$ integers, where the $i$-th integer represents the weight $a_i$ of node $i$.

Output

Output $n$ lines, where the $i$-th line contains the answer for node $i$.

Examples

Input 1

10
1 1 2 3 2 3 6 7 7
10 6 4 10 8 10 5 3 5 4

Output 1

0
15
12
15
15
15
14
15
15
15

Subtasks

Idea: nzhtl1477, Solution: zx2003, Code: nzhtl1477, Data: nzhtl1477

For $10\%$ of the data, $1 \le n \le 10^2$.

For another $20\%$ of the data, $1 \le n \le 10^4$.

For another $30\%$ of the data, the tree is a chain.

For another $20\%$ of the data, $0 \le a_i \le 10^2$.

For $100\%$ of the data, $1 \le n \le 5 \times 10^5$ and $0 \le a_i \le 10^{18}$.