Груша на Хэллоуин

При подготовке к Хэллоуину Джек подумал, что тыквы --- это прошлый век, надо готовить груши (действительно, почему бы и нет, форма похожая)! Возможно, это связано с тем, что тыквы он не выращивает, но зато у него есть грушевое дерево. И к празднику на этом дереве выросло $n$ груш, каждая размером $a\_i$.

Грушевое дерево также является деревом в том смысле, что является связным неориентированным графом без циклов. Одна из груш расположилась прямо около корня дерева (не спрашивайте как так получилось), а каждая следующая располагается на ветке, растущей из места крепления одной из предыдущих груш.

Детишки, которые пришли к Джеку за конфетами, только сегодня на уроке информатики прошли операцию XOR (обозначается $\oplus$) --- побитовое исключающее <<или>>. Будучи в хорошем настроении, Джек предложил им заработать больше конфет, посчитав на его грушевом дереве следующую величину: \begin{enumerate}

1. Рассматривается путь между двумя грушами $i$ и $j$. За вес такого пути обозначается сумма весов груш, висящих на его концах, то есть $a\_i + a\_j$.
2. Для всех путей в дереве, у которых номер первой груши меньше номера последней груши, рассматривается их вес, и к ним всем применяется XOR, то есть получается $\bigoplus\limits\_{\substack{i \rightsquigarrow j \\\ i < j}} a\_i + a\_j$

Именно столько конфет получат дети, если смогут посчитать эту величину. Помогите им в этом, и, возможно, они даже поделятся с вами!

В первой строке ввода находится единственное целое число $n$ ($1 \leq n \leq 3 \cdot 10^5$) --- количество груш на дереве.

В следующей строке через пробел перечислены $n$ целых чисел $a\_i$ ($1 \leq a\_i \leq 10^{18}$) --- размеры груш.

В следующих $n - 1$ строках находятся описания веток дерева, в $i$-й строке через пробел даны два целых числа $v\_i$ и $u\_i$ --- номера груш, между которыми растет $i$-я ветка дерева ($1 \leq a\_i, b\_i \leq n$).

Выведите единственное целое число --- XOR весов всех путей в дереве.