For a tree $X$, rooted at node $1$, having values at nodes, and a node $i$, lets define $S(X, i)$ as the bitwise xor $(\oplus)$ of all values in the subtree of node $i$.

You are given a tree $T$. Let $T_i$ be the tree remaining after removing all nodes in subtree of $i$. Define $P(i) = \displaystyle \text{max}_{j \in T_i} (S(T, i) \oplus S(T_i, j) )$. You have to find sum of $P(i)$ over all nodes $i \neq 1$.

Input:

First line contains a single integer $N$, denoting the number of nodes in the tree $T$. Next line contains $N$ space separated integers denoting the values of nodes in the tree $G$, $i^{\text{th}}$ integer being the value of node $i$. Each of the next $N - 1$ lines contain $2$ space separated integers $A$ and $B$, meaning that there is an edge from node $A$ to node $B$.

Output:

Print a single integer, the sum of $P(x)$ for all nodes $x$ (except $1$) of the tree $G$.

Constraints:

$2 \le N \le 2 \times 10^5$

$1 \le A, B \le N$

$1 \le G_i \le 10^9$