给一棵根为 $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

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