Xorability P43845

Consider a tree with $n$ nodes numbered from 1 to $n$, rooted at 1. Each node $i$ has a natural label $\ell_i$. Given two nodes $u$ and $v$, define $X(u, v)$ as the exclusive or (^ in C++) of all the $\ell_i$ in the path from $u$ to $v$.

Let $L$ be the set of leaves of the tree. Please compute $\sum_{v \in L} X(1, v)$.

Input

Input consists of several trees, each with the number of nodes $n$, followed by $\ell_1, \dots, \ell_n$, followed by $n - 1$ pairs of nodes describing the edges of the tree. Assume $2 \le n \le 10^5$, and $0 \le l_i \le 10^9$.

Output

For each tree, print the required sum.