Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D2T3. $\texttt{1s,0.5G}$.

Happy Birthday to NaCly_Fish! (2024.7.28)

Problem Description

Jura has $N$ squares, numbered $1$ to $N$. The $i$-th square has a side length of $a_i$, and $a_i$ is even. Initially, all squares are black.

Jura decides to spend $(N-1)$ seconds playing with these squares. At the $i$-th second, Jura merges the $x_i$-th and $y_i$-th squares into the $(N+i)$-th square (after merging, the $x_i$-th and $y_i$-th squares no longer exist).

When merging squares, the centers of the two squares are aligned, and their edges are parallel in the plane. The size of the new square is the larger of the two merged squares; its color is the "XOR sum" of the original two squares' colors (black + black = white, white + white = white, black + white = black, white + black = black). The cost of merging squares is the area of the intersection of the two squares that is black in both squares before merging (but after they are positioned as described).

You need to output the cost of each merging operation.

Below is an example of square merging:

Input Format

The first line contains a positive integer $N$, the number of squares.

The second line contains $N$ positive integers describing the sequence $a$.

The next $(N-1)$ lines each contain two positive integers $x_i, y_i$, describing an operation.

Output Format

Output $(N-1)$ lines, each containing an integer representing the cost of the operation.

Sample Input and Output

Input Sample #1

6 
8 6 2 4 2 6
1 2
3 4
5 7
6 8
9 10

Output Sample #1

36
4
0
12
4

Input Sample #2

7 
4 2 6 6 2 4 2
1 2
3 8
4 9
5 10
6 11
7 12

Output Sample #2

4
12
24
0
16
0 

Input Sample #3

8
4 10 2 10 6 8 4 12
1 2
3 4
5 6
7 8
9 10
11 12
13 14

Output Sample #3

16
4
36
16
84
28
0

Notes

Sample Explanation

The last operation of Sample 1 is illustrated below:

Data Range

For $100\%$ of the data, it is guaranteed that:

• $1 \le N \le 10^5$;
• $2 \le a_i \le 10^6$.
• $a_i$ is even.
• $1 \le x_i, y_i \le N+i-1$
• The squares exist before the operation, and $x_i \neq y_i$.

见题面 Input 部分

见题面 Output 部分