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$$