You are given $N$ squares labeled with numbers from $1$ to $N$. A square with label $i$ has a side length $a_i$, where $a_i$ is an even number. Initially, every square is colored black.
Jura has a coordinate system and has decided to spend $N - 1$ seconds of his life working with these squares. In the $i$-th second, Jura takes the squares with labels $x_i$ and $y_i$ and joins them into a new square with label $N + i$ (after joining, the squares with labels $x_i$ and $y_i$ no longer exist).
When joining two squares, Jura places them in the coordinate system such that their centers are at $(0, 0)$ and their sides are parallel to the axes. The new square will have dimensions equal to the larger of the two squares being joined, and it will be colored in the following way: if a point is black in both squares or white in both squares, it will be white in the new square; otherwise, it will be black.
Joining, of course, is not free; the cost of joining is equal to the area of all points that are black in both squares simultaneously. Jura is interested in the cost of each of the $N - 1$ joins he made. The images show examples of joining.
Input
The first line contains a natural number $N$, the number of squares.
The second line contains a sequence of natural numbers $a_1, a_2, \dots, a_N$ representing the side lengths of the given squares.
The next $N - 1$ lines each contain 2 numbers; the $i$-th of these $N - 1$ lines contains the numbers $x_i$ and $y_i$, the labels of the squares that Jura joined in the $i$-th second.
Output
Print $N - 1$ lines. In the $i$-th line, print a single number, the cost of the $i$-th join.
Subtasks
In all subtasks, $1 \le N \le 10^5$, $2 \le a_i \le 10^6$, $a_i$ is even for all $i = 1, 2, \dots, N$, $1 \le x_i, y_i \le N + i - 1$, for all $i = 1, 2, \dots, N - 1$, and all $x_i$ and $y_i$ are distinct.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 14 | $N \le 5000$ |
| 2 | 25 | $x_1 = 1, y_1 = 2, x_i = i + 2, y_i = N + i - 1$ for all $i = 2, 3, \dots, N$ |
| 3 | 17 | $N$ is a power of $2, x_i = 2i - 1, y_i = 2i$ |
| 4 | 21 | $N \le 30000$ |
| 5 | 23 | No additional constraints. |
Examples
Input 1
6 8 6 2 4 2 6 1 2 3 4 5 7 6 8 9 10
Output 1
36 4 0 12 4
Input 2
7 4 2 6 6 2 4 2 1 2 3 8 4 9 5 10 6 11 7 12
Output 2
4 12 24 0 16 0
Input 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 3
16 4 36 16 84 28 0
Note
Explanation of the first example: The last join is shown in the image: