Yet Another XOR Problem

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

3
4 7 15
1 2
3 1

11

5
11 3 7 6 14
1 2
2 3
3 4
2 5

13