Дано дерево. У i-ої вершини є значення ai.Вiдстань мiж двома вершинами — це xor a i всiх вершин на шляху.Знайдiть суму вiдстаней мiж вершинами u та v такими, що 1≤u≤v≤n.
Перший рядок мiстить одне цiле число n(1≤n≤105) — кiлькiсть вершин.Другий рядок мiстить n цiлих чисел a1 , a2 , . . . , an (0≤ai≤106).Кожен з наступних n − 1 рядкiв мiстить по два цiлi числа ui та vi (1 ≤ ui , vi ≤ 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.