XOR

Дано дерево, у кожної вершини $i$ є значення a_i. Відстань між двома вершинами визначається як XOR усіх значень на шляху між ними. Ваше завдання — знайти суму відстаней для всіх пар вершин $(u,v)$ таких, що 1 \leq u \leq v \leq n.

\InputFileПерший рядок містить ціле число $n$ (1 \leq n \leq 10^5) — кількість вершин у дереві.

Другий рядок містить $n$ цілих чисел a_1, a_2, \ldots, a_n (0 \leq a_i \leq 10^6) — значення у вершинах.

Кожен з наступних n-1 рядків містить по два цілих числа u_i і v_i (1 \leq u_i, v_i \leq n), які задають ребро між вершинами u_i і v_i.

\OutputFileВиведіть одне число — суму відстаней між усіма парами вершин $(u,v)$, де 1 \leq u \leq v \leq n.

\NoteНаприклад, для наведеного дерева:

• Відстань від вершини $1$ до $1$ — $1$.

• Відстань від вершини $1$ до $2$ — $3$.

• Відстань від вершини $1$ до $3$ — $0$.

• Відстань від вершини $2$ до $2$ — $2$.

• Відстань від вершини $2$ до $3$ — $1$.

• Відстань від вершини $3$ до $3$ — $3$.

Сума цих відстаней дорівнює 1 + 3 + 0 + 2 + 1 + 3 = 10.