XOR

Given a tree where each vertex $i$ has an associated value $a_i$, the distance between two vertices is defined as the XOR of all vertex values along the path connecting them. Your task is to calculate the sum of distances for all pairs of vertices $(u,v)$ such that $1\le u\le v\le n$.

Input Format

• The first line contains a single integer $n$ $(1\le n\le 10^5)$, representing the number of vertices in the tree.

• The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(0\le a_i\le 10^6)$, which are the values associated with each vertex.

• Each of the following $n-1$ lines contains two integers $u_i$ and $v_i$ $(1\le u_i,v_i\le n)$, indicating an edge between vertices $u_i$ and $v_i$.

Output Format

• Output a single integer, which is the sum of distances between all pairs of vertices $(u,v)$ with $1\le u\le v\le n$.

Examples

Note

For example, consider the following calculations for a given tree:

• The distance from vertex 1 to 1 is 1.

• The distance from vertex 1 to 2 is 3.

• The distance from vertex 1 to 3 is 0.

• The distance from vertex 2 to 2 is 2.

• The distance from vertex 2 to 3 is 1.

• The distance from vertex 3 to 3 is 3.

The total sum of these distances is $1+3+0+2+1+3=10$.