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

Let L be the set of leaves of the tree.
Please compute ∑_{v ∈ L} X(1, v).

Input

Input consists of several trees,
each with the number of nodes n,
followed by ℓ_{1}, …, ℓ_{n},
followed by n − 1 pairs of nodes describing the edges of the tree.
Assume 2 ≤ n ≤ 10^{5},
and 0 ≤ l_{i} ≤ 10^{9}.

Output

For each tree, print the required sum.

Public test cases

**Input**

3 2 7 3 1 2 2 3 6 18 6 9 12 15 3 1 6 6 5 3 6 2 3 3 4 7 1 2 3 4 5 6 7 1 4 1 5 2 1 4 6 2 3 2 7 4 1000000000 0 0 0 2 1 3 1 4 1

**Output**

6 80 11 3000000000

Information

- Author
- Ángel García
- Language
- English
- Official solutions
- C++
- User solutions
- C++