Tree XOR 1

You are given a tree consisting of \(N\) nodes and each consist value \(A_i\). You have to find the Maximum XOR of all paths.

Input Format

The first line contains an integer \(N\) denotes the number of nodes. The next \(N - 1\) line contains \(2\) space-separated integers denoting the connection between nodes. The next line contains \(N\) integers denoting \(A_i\).

Output Format

Print the maximum XOR.

Constraints

\(1 \le N \le 3 * 10 ^ 4\)
\(0 \lt A_i \le 10 ^ {16}\)

Subtasks
\((24 points) 1 \le N \le 500\)
\((32 points) 1 \le N \le 5 * 10 ^ 3\)
\((40 points) 1 \le N \le 10 ^ 4\)
\((4 points) 1 \le N \le 3 * 10 ^ 4\)

Limits

• Time - 3 Seconds
• Memory - 512MB

Sample Input 0

5
1 3
2 4
3 2
4 5
2 8 8 4 1

Sample Output 0

13