Problem Description

How wonderful! The starting point and the destination cannot be decided, and the game ends halfway. The light of the end shines upon the earth, and students in the school begin to go to the cafeteria to buy hamburgers.

You have $n$ hamburgers, where each hamburger $i$ has a deliciousness value $a_i$. You can place these hamburgers arbitrarily on the $n$ nodes of a tree, such that each node contains exactly one hamburger. The hamburgers at school are so delicious, so we define the total deliciousness as follows: for every chain on the tree leading to the root node $1$, calculate the XOR sum of the deliciousness values of the hamburgers on that chain. The total deliciousness is the bitwise AND sum of all these XOR results.

What is the maximum total deliciousness you can obtain after placing the hamburgers on the tree in an optimal way?

I suddenly... really want... to eat... a hamburger...

Original Formal Problem Statement:

There is a tree with $n$ nodes, numbered from $1$ to $n$, with the root node being $1$; and a sequence $a$ of length $n$.

You can arbitrarily rearrange the sequence $a$, and then sequentially assign the node weight of node $i$ on the tree to be $a_i$, in order to maximize the value of this tree.

We define $f(i)$ as the XOR sum of the node weights (including the node itself) on the simple path from node $i$ to the root of the tree. Then, the value of the tree is defined as: $\operatorname{AND}_{i=1}^{n}f(i)$. That is, the bitwise AND sum of $f(i)$ for nodes $1$ to $n$.

Input Format

The first line contains a positive integer $n$.

The next line contains $n$ positive integers representing the sequence $a$.

The following $n-1$ lines each contain two integers $u$ and $v$, indicating that there is an edge between node $u$ and node $v$. It is guaranteed that the graph is a tree.

Output Format

Output a single non-negative integer on one line, representing the maximum value of the tree.

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

2

Hint

This problem uses bundled testing.

For all test data, the following conditions apply:

• $1 \leq u,v \leq n \leq 10^5$.
• $1 \leq a_i \leq 10^9$.

Translated by Qwen 3.6