Un árbol tiene \(n\) nodos, numerados de \(0\) a \(n - 1\), y cada nodo tiene un valor. Se quitan dos aristas distintas, lo que deja tres componentes. Para cada componente se calcula el XOR de los valores de sus nodos; el puntaje de esa elección es el mayor de los tres XOR menos el menor. Encuentra el menor puntaje posible.

Entrada

La primera línea tiene \(n\) \((3 \le n \le 1000)\). La segunda tiene los valores, entre \(1\) y \(10^8\). Cada una de las siguientes \(n - 1\) líneas tiene una arista \(a\) \(b\).

Salida

El menor puntaje.

Ejemplo 1

Entrada

5
1 5 5 4 11
0 1
1 2
1 3
3 4

Salida

9

Ejemplo 2

Entrada

6
5 5 2 4 4 2
0 1
1 2
5 2
4 3
1 3

Salida

0