Given a rooted tree $T$ with $n$ nodes, where nodes are numbered from $1$ to $n$ and the root is node $1$. Each node $i$ has a positive integer weight $v_i$.

Let the set of nodes in the subtree of node $x$ (including $x$ itself) be $c_1, c_2, \dots, c_k$. The value of $x$ is defined as:

$$ val(x) = (v_{c_1} + d(c_1, x)) \oplus (v_{c_2} + d(c_2, x)) \oplus \cdots \oplus (v_{c_k} + d(c_k, x)) $$

where $d(x, y)$ denotes the number of edges on the unique simple path between node $x$ and node $y$ in the tree, with $d(x, x) = 0$. The symbol $\oplus$ denotes the bitwise XOR operation.

Calculate the result of $\sum_{i=1}^n val(i)$.

Input

The first line contains a positive integer $n$, representing the size of the tree.

The second line contains $n$ positive integers, representing the weights $v_i$.

The next line contains $n-1$ positive integers, representing the parent $p_i$ of each node from $2$ to $n$ in order.

Output

Output a single integer representing the answer.

Examples

Input 1

5
5 4 1 2 3
1 1 2 2

Output 1

12

Note 1

$val(1) = (5 + 0)\oplus(4 + 1)\oplus(1 + 1)\oplus(2 + 2)\oplus(3 + 2) = 3$.

$val(2) = (4 + 0)\oplus(2 + 1)\oplus(3 + 1) = 3$.

$val(3) = (1 + 0) = 1$.

$val(4) = (2 + 0) = 2$.

$val(5) = (3 + 0) = 3$.

The sum is $12$.

Input 2

See the provided files.

Subtasks

$10\%$ of the data: $1\le n\le 2\,501$.

$40\%$ of the data: $1\le n\le 152\,501$.

An additional $20\%$ of the data: all $p_i = i - 1$ ($2\le i\le n$).

An additional $20\%$ of the data: all $v_i = 1$ ($1\le i\le n$).

$100\%$ of the data: $1\le n, v_i \le 525\,010, 1\le p_i\le n$.