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

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

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

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

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

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

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

满足 $n≤5×10^5,1≤A_i≤10^6$

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

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