该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

给一棵根为 $ 1 $ 的有根树，点 $ i $ 具有一个权值 $ A_i $ 。

定义一个点对的值 $ f(u,v) = \max(A_u, A_v) \times |A_u - A_v| $ 。

你需要对于每个节点 $ i $ ，计算 $ ans_i = \sum_{u\in subtree(i), v\in subtree(i)} f(u,v) $ ，其中 $ subtree(i) $ 表示 $ i $ 的子树。

请你输出 $ \oplus (ans_i \mod 2^{64}) $ ，其中 $ \oplus $ 表示 XOR。

Input

第一行输入一个 $ n $，表示树的节点个数。

接下来 $ n-1 $ 行输入 $ u_i, v_i $，表示树边。

然后输入一行 $n$ 个数字 $ A_i $，表示点 $i$ 的权值。

满足 $n \leq 5 \times 10^5, 1 \leq A_i \leq 10^6$

Output

输出一个数字，表示答案。

10
1 2
2 3
3 4
1 5
4 6
1 7
5 8
4 9
9 10
2 7 3 7 9 7 4 7 3 8

1130

Hint

答案分别是1918 544 416 224 36 0 0 0 80 0