大约三十年前，年轻的 Krešo 第一次参加了全国信息学竞赛。与今天类似，竞赛的开幕式由一系列发言人组成，他们试图通过励志演讲向参赛者展示这项赛事的重要性。观众们热情高涨，每隔几秒钟就开心地鼓掌，但 Krešo 却被其中一句话激怒了。具体来说，其中一位发言人声称，他更欣赏逻辑“与”（AND）运算，而不是逻辑“或”（OR）运算，因为无论获胜者的身份如何，对他来说，Mirko 和 Slavko 都是全国竞赛的获胜者，而不是获胜者是 Mirko 或 Slavko。Krešo 气疯了，站起来开始向观众解释，这是一种被称为“异或”（exclusive OR，俗称 XOR）的运算。在结束他的演讲后，他给这位杰出的发言人留下了以下任务，以检验他的理解。
给定一棵由 $N$ 个节点组成的树，其中每个节点都被分配了一个权值。树上一条路径的权值定义为该路径上所有节点权值的异或和（exclusive OR）。你的任务是求出树上所有路径的权值之和，包括仅包含一个节点的路径。
三十年后，Krešo 终于说服了 COCI 的命题组将这个任务加入到其中一轮比赛中。请帮助我们重拾 Krešo 对竞争性程序设计未来的信心。
注意：异或（$\oplus$）是一种二进制运算，它分别应用于其两个操作数的每个对应位，当且仅当两个操作数中恰好有一个操作数的该位为 1 时，结果中的该位才被设置为 1。
输入格式
第一行包含一个正整数 $N$ ($1 \le N \le 100\,000$)，表示树中的节点数。
第二行包含 $N$ 个由空格隔开的整数 $v_i$ ($0 \le v_i \le 3\,000\,000$)，第 $i$ 个值表示第 $i$ 个节点的权值。
接下来的 $(N-1)$ 行，每行包含两个数 $a_j$ 和 $b_j$ ($1 \le a_j, b_j \le N$)，表示节点 $a_j$ 和 $b_j$ 之间存在一条边。
输出格式
输出所有树上路径权值的总和。
子任务
- 在占总分 30% 的测试数据中，$N$ 将小于或等于 200。
- 在占总分 50% 的测试数据中，$N$ 将小于或等于 1000。
- 在占总分额外 20% 的测试数据中，每个节点 $x = 1, 2, \dots, N-1$ 都与节点 $x + 1$ 相连。
样例
输入样例 1
3 1 2 3 1 2 2 3
输出样例 1
10
输入样例 2
5 2 3 4 2 1 1 2 1 3 3 4 3 5
输出样例 2
64
输入样例 3
6 5 4 1 3 3 3 3 1 3 5 4 3 4 2 2 6
输出样例 3
85
说明
第一个样例的解释：
- 节点 1 到节点 1 的路径权值为 $1$
- 节点 1 到节点 2 的路径权值为 $1 \oplus 2 = 3$
- 节点 1 到节点 3 的路径权值为 $1 \oplus 2 \oplus 3 = 0$
- 节点 2 到节点 2 的路径权值为 $2$
- 节点 2 到节点 3 的路径权值为 $2 \oplus 3 = 1$
- 节点 3 到节点 3 的路径权值为 $3$
所有路径的权值之和为 $1 + 3 + 0 + 2 + 1 + 3 = 10$。