28571번 - Груша на Хэллоуин 다국어

문제

При подготовке к Хэллоуину Джек подумал, что тыквы --- это прошлый век, надо готовить груши (действительно, почему бы и нет, форма похожая)! Возможно, это связано с тем, что тыквы он не выращивает, но зато у него есть грушевое дерево. И к празднику на этом дереве выросло $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 весов всех путей в дереве.

제한

힌트