XOR

Дано дерево. У $i$-ої вершини є значення $a_i$.Вiдстань мiж двома вершинами — це $xor$ a i всiх вершин на шляху.Знайдiть суму вiдстаней мiж вершинами $u$ та $v$ такими, що $1\le u\le v\le n$.

Вхідні дані

Перший рядок мiстить одне цiле число $n(1\le n\le 10^5)$ — кiлькiсть вершин.Другий рядок мiстить n цiлих чисел $a_1$ , $a_2$ , . . . , $a_n$ ($0\le a_i\le 10^6$).Кожен з наступних n − 1 рядкiв мiстить по два цiлi числа $u_i$ та $v_i$ (1 ≤ $u_i$ , $v_i$ ≤ n).

Вихідні дані

Виведiть вiдповiдь на задачу.

####Примiтка

У першому прикладi рiшення таке:

• з 1 в 1 вiдстань 1,

• з 1 в 2 вiдстань 3,

• з 1 в 3 вiдстань 0,

• з 2 в 2 вiдстань 2,

• з 2 в 3 вiдстань 1,

• з 3 в 3 вiдстань 3.

Сумарна вiдстань рiвна $1+3+0+2+1+3=10$.

Приклади