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 \leq u \leq v \leq n.

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

The second line contains $n$ integers a_1, a_2, \ldots, a_n (0 \leq a_i \leq 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 \leq u_i, v_i \leq n), indicating an edge between vertices u_i and v_i.

\OutputFileOutput a single integer: the sum of distances between all pairs of vertices $(u,v)$ such that 1 \leq u \leq v \leq n.

\NoteFor 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.