Jura's Square Merging Game

Jura has \(N\) squares numbered from \(1\) to \(N\). The \(i\)-th square has a side length \(a_i\) (an even number). Initially, all squares are black.

Jura spends \(N-1\) seconds playing with these squares. In the \(i\)-th second, he merges the squares numbered \(x_i\) and \(y_i\) to form a new square labelled \(N+i\) (after the merge, the squares \(x_i\) and \(y_i\) no longer exist). The merge is performed as follows:

• The two squares are arranged so that their centers coincide and their edges remain parallel to the coordinate axes.
• The new square's side length is \(\max(a, b)\), where \(a\) and \(b\) are the side lengths of the two merged squares.
• The new square's color is the "xor" of the two original colors. Formally, if we denote black as 1 and white as 0, then the new color is \(c_1 \oplus c_2\). In other words, merging two squares of the same color (black+black or white+white) results in a white square, while merging squares of different colors (black+white or white+black) results in a black square.
• The cost of a merge is defined as the area of the region that is black in both pre-merged squares within the overlapping area. Since the squares are centered and aligned, their intersection is a square with side length \(\min(a, b)\). Hence, the cost is \(\min(a, b)^2\) if both squares are black, and \(0\) otherwise.

Your task is to output the cost of each merge operation.

Note: The colors update immediately after each merge, so subsequent operations will use the newly formed squares.

inputFormat

The first line contains an integer \(N\) representing the number of squares.

The second line contains \(N\) even integers \(a_1, a_2, \dots, a_N\), where \(a_i\) is the side length of the \(i\)-th square.

Then \(N-1\) lines follow. The \(i\)-th of these lines contains two integers \(x_i\) and \(y_i\) indicating that at second \(i\), the squares with these labels are merged to form square \(N+i\).

outputFormat

Output \(N-1\) lines. The \(i\)-th line should contain a single integer representing the cost of the \(i\)-th merge operation.

sample

4
2 4 6 8
1 2
3 5
4 6

4
0
36