Sayadpur City

Bob wants to visit a new country called sayadpur. There are $N$ cities ($1, 2, 3, …, N$) in sayadpur, and they are connected by $N-1$ undirected roads. You can go from one city to any other city using these roads. Each city except city 1 is directly connected with at most two cities. Bob wants to start his journey from a city and then move to any adjacent city. In his journey, he does not want to visit a city twice. For visiting a city he has to pay a cost. Suppose he visits total $k$ cities and the cost of those cities are $a_1,a_2, …, a_k$.

The overall cost will be the bitwise “or” of those costs ($a_1 | a_2 | a_3 | … | a_k$). You have to find the maximum overall cost.

Input

First-line there is a number $N$ ( $1 ≤ N ≤ 10^5$ ).

Each of the next $N-1$ lines contains two integers $u$ and $v$ ($1 ≤ u, v ≤ n$ and $u≠v$), denoting an edge connecting vertex $u$ and vertex $v$. Next line contains $N$ integers $a_1, a_2, …, a_N$ ($1 ≤ a_i ≤ 2047$ and $1 ≤ i ≤ N$). The first element is the cost of city number 1, the second element is the cost of city number 2 city and so on.

Output

Output one integer, the maximum overall cost.

Sample

Input	Output
3 1 2 1 3 1 2 4	7