Problems
XOR
XOR
Дано дерево. У i-ої вершини є значення a_i.Вiдстань мiж двома вершинами — це xor a i всiх вершин на шляху.Знайдiть суму вiдстаней мiж вершинами u та v такими, що 1 ≤ u ≤ v ≤ n.
Input data
Перший рядок мiстить одне цiле число n (1 ≤ n ≤ 10^5) — кiлькiсть вершин.Другий рядок мiстить n цiлих чисел a_1 , a_2 , . . . , a_n (0 ≤ a_i ≤ 10^6).Кожен з наступних n − 1 рядкiв мiстить по два цiлi числа u_i та v_i (1 ≤ u_i , v_i ≤ n).
Output data
Вивед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.
Examples
Input example #1
3 1 2 3 1 2 2 3
Output example #1
10
Input example #2
5 1 2 3 4 5 1 2 2 3 3 4 3 5
Output example #2
52
Input example #3
5 10 9 8 7 6 1 2 2 3 3 4 3 5
Output example #3
131