XOR

Дано дерево. У каждой вершины $i$ есть значение $a_i$. Расстояние между двумя вершинами определяется как $xor$ всех значений на пути между ними. Ваша задача — найти сумму расстояний для всех пар вершин $(u,v)$, где $1\le u\le v\le n$.

Формат входных данных

Первая строка содержит одно целое число $n$ $(1\le n\le 10^5)$ — количество вершин в дереве. Вторая строка содержит $n$ целых чисел $a_1,a_2,\dots ,a_n$ $(0\le a_i\le 10^6)$, которые представляют значения в вершинах. Каждая из следующих $n-1$ строк содержит по два целых числа $u_i$ и $v_i$ $(1\le u_i,v_i\le n)$, обозначающих ребро между вершинами $u_i$ и $v_i$.

Формат выходных данных

Выведите одно число — сумму всех расстояний между парами вершин $(u,v)$.

Примеры

Примечание

В первом примере:

• Расстояние от 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$.