Orange Farm Simulation

Bru is playing an orange farm simulation game. After playing for a long time, Bru has built $N$ orange fields on the farm, and the fields are connected by $N-1$ roads so that every field can be reached from every other field.

As the farm grows, Bru wants to cut one road to split the farm in two. Splitting the farm lets both halves grow at the same time, so efficiency goes up. However, once the farm is split, the fields on opposite sides enter a competitive relationship. Field $i$ has competitiveness $A_i$. If field $i$ and field $j$ are in a competitive relationship, the competition index between them is $A_i \oplus A_j$, where $\oplus$ is bitwise XOR. The total competition index for cutting one road is the maximum competition index over all competitive pairs created by that cut.

For example, take the farm in the figure above with $A_i = i$, and cut the road between fields 2 and 3, as in the figure below.

The competition indices of all competitive pairs are:

• Field 3 with fields 1, 2, 4, and 7: 2, 1, 7, 4
• Field 5 with fields 1, 2, 4, and 7: 4, 7, 1, 2
• Field 6 with fields 1, 2, 4, and 7: 7, 4, 2, 1

The maximum is 7, so the total competition index for cutting the road between fields 2 and 3 is 7.

Write a program that computes the total competition index for cutting each road.

The first line contains the number of fields $N$.

The second line contains the competitiveness of each field, $A_1, A_2, \cdots, A_N$.

From the third line to line $N+1$, line $i+2$ contains the numbers of the two fields $u_i$ and $v_i$ joined by road $i$, in the form $u_i \ v_i$.

Print the total competition index for cutting each road, from road 1 to road $N-1$, one per line, in order.

• $2 \le N \le 2 \times 10^5$
• $0 \le A_i < 2^{20}$
• $1 \le u_i, v_i \le N$
• $u_i \ne v_i$
• Every field can be reached from every other field through the given roads.