Given a rooted tree with N nodes where each node has a value, find a pair of nodes (u, v) so that u is an ancestor of v and the bit-wise XOR of the values of u and v is the maximum among all such pairs. The tree is always rooted at node 1.
A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. An ancestor of a node is any node in the path from that node to the root node (including the root node itself).
Input
The first line will contain a single integer N (2 ≤ N ≤ 5×105), the number of nodes in the tree.
The second line will contain N integers, the values of the nodes. Values will be between 0 and 109 inclusive.
The following N-1 lines will contain edges ui and vi (1 ≤ ui, vi ≤ N). Input is guaranteed to form a valid tree.
Output
Print the required maximum bit-wise XOR in a single line.
Samples
| Input | Output |
|---|---|
3 4 7 15 1 2 3 1 | 11 |
| Input | Output |
|---|---|
5 11 3 7 6 14 1 2 2 3 3 4 2 5 | 13 |
