오렌지 농장 시뮬레이션

브루는 오렌지 농장 시뮬레이션 게임을 하고 있다. 오랜 시간 게임을 진행하면서 브루는 농장에 오렌지 밭 $N$개를 만들었고, 이 밭들을 $N-1$개의 도로로 연결해 어느 밭에서든 다른 모든 밭으로 갈 수 있게 했다.

농장의 규모가 커지자 브루는 도로 하나를 끊어 농장을 둘로 나누려고 한다. 농장을 둘로 나누면 양쪽이 동시에 성장하므로 효율이 높아진다. 다만 농장이 둘로 나뉘면 양쪽의 밭들은 경쟁 관계에 놓인다. $i$번 밭의 경쟁력은 $A_i$이고, $i$번 밭과 $j$번 밭이 경쟁 관계이면 두 밭 사이의 경쟁 지수는 $A_i \oplus A_j$이다. 여기서 $\oplus$는 비트 XOR을 뜻한다. 도로 하나를 끊었을 때의 총 경쟁 지수는 그 끊김으로 생기는 모든 경쟁 관계의 경쟁 지수 중 최댓값이다.

예를 들어 위 그림의 농장에서 $A_i = i$이고, 2번 밭과 3번 밭 사이의 도로를 끊어 아래 그림과 같이 되었다고 하자.

이때 생기는 모든 경쟁 관계의 경쟁 지수는 다음과 같다.

• 3번 밭과 1, 2, 4, 7번 밭의 경쟁 지수: 2, 1, 7, 4
• 5번 밭과 1, 2, 4, 7번 밭의 경쟁 지수: 4, 7, 1, 2
• 6번 밭과 1, 2, 4, 7번 밭의 경쟁 지수: 7, 4, 2, 1

이 중 최댓값은 7이므로, 2번 밭과 3번 밭 사이의 도로를 끊었을 때의 총 경쟁 지수는 7이다.

각 도로를 끊었을 때의 총 경쟁 지수를 모두 계산하는 프로그램을 작성해야 한다.

첫 줄에는 오렌지 밭의 수 $N$이 주어진다.

둘째 줄에는 각 밭의 경쟁력 $A_1, A_2, \cdots, A_N$이 주어진다.

셋째 줄부터 $N+1$번 줄까지, $i+2$번 줄에는 $i$번 도로가 잇는 두 밭의 번호 $u_i$, $v_i$가 $u_i \ v_i$의 형태로 주어진다.

각 도로를 끊었을 때의 총 경쟁 지수를 1번 도로부터 $N-1$번 도로까지 차례로 한 줄에 하나씩 출력한다.

• $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$
• 주어진 도로를 통해 모든 밭 사이를 오갈 수 있다.