# Yet Another XOR Problem

Criterion 2020 Round 3
Limits 3s, 1.0 GB

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

InputOutput
3
4 7 15
1 2
3 1


11

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

13