喜大普奔！喜大普奔！R0终于做出了无振听的纯正九莲宝灯！因此猫粮工作室送了他一颗树，但他必须解决树上的问题才能得到他心爱的一姬。为了不让R0失去一姬，你能帮助他吗？
你将得到一棵树，由n-1条边连接的n个顶点组成的无向无环图，树的根为顶点1。
每个顶点i都分配有一个美丽度w[i]，我们定义路径的美丽度F(u, v)函数，F(u, v)为u与v之间最短路径上所有顶点的美丽度的异或和，其中u为v的祖先。
例如w[1]，w[2]，w[3]， …，w[k] 是u和v之间最短路径上的各个顶点的美丽度，则F(u, v) = w[1]^w[2]^w[3]^...^w[k]，其中"^"表示异或运算符。
由于美丽度函数F(u, v)并不美丽，于是一姬定义了超级美丽度函数S(u, v)，S(u, v) = F(u, v) * v。
R0现在想知道S(u1, v1) ^ S(u2, v2)的最大值。(1 ≤ u1, v1, u2, v2 ≤ n)
Hint : 定义一个顶点的祖先为：如果顶点u位于根和v之间的最短路径上，则它称为v的祖先。(注意：当u等于v时，u也是v的祖先) 题中所有"^"表示异或运算符。
单组数据
第一行包含一个整数n（1≤ n ≤20000）树中的顶点数
以下n - 1行描述了树的边，每行包含两个整数u，v（1 ≤ u，v ≤ n，u ≠ v）
最后一行包含n个整数w[1]，w[2]，…，w[n]（0 ≤ w[i] ≤15),表示每个节点的美丽值。
n的总和不超过100000。
输出S(u1, v1) ^ S(u2, v2)的最大值
5 1 2 1 3 1 4 4 5 4 5 6 0 8
62