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

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

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

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

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