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

Формат вхiдних даних

Перший рядок м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).

Формат вихiдних даних

Вивед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$.