给定 $N$ 个正方形，编号从 $1$ 到 $N$。编号为 $i$ 的正方形边长为 $a_i$，其中 $a_i$ 为偶数。初始时，每个正方形都被涂成黑色。

Jura 拥有一个坐标系，他决定花费 $N-1$ 秒的时间来处理这些正方形。在第 $i$ 秒，Jura 取出编号为 $x_i$ 和 $y_i$ 的正方形，并将它们合并成一个编号为 $N+i$ 的新正方形（合并后，编号为 $x_i$ 和 $y_i$ 的正方形不再存在）。

在合并两个正方形时，Jura 将它们放置在坐标系中，使得它们的中心均位于 $(0, 0)$，且边与坐标轴平行。新正方形的尺寸将等于被合并的两个正方形中较大的那一个。新正方形的颜色规则如下：如果某一点在两个正方形中均为黑色或均为白色，则在新正方形中该点为白色；否则，该点为黑色。

合并操作并非免费，合并的代价等于两个正方形中同时为黑色的所有点的面积之和。Jura 想知道他所做的 $N-1$ 次合并中，每一次的代价是多少。下图展示了合并的示例。

输入格式

第一行包含一个自然数 $N$，表示正方形的数量。

第二行包含一个自然数序列 $a_1, a_2, \dots, a_N$，表示给定正方形的边长。

接下来的 $N-1$ 行，每行包含两个数字。第 $i$ 行中的两个数字 $x_i$ 和 $y_i$ 表示 Jura 在第 $i$ 秒合并的正方形编号。

输出格式

输出 $N-1$ 行。第 $i$ 行输出一个数字，表示第 $i$ 次合并的代价。

子任务

在所有子任务中，满足 $1 \le N \le 10^5$，$2 \le a_i \le 10^6$，$a_i$ 对于所有 $i = 1, 2, \dots, N$ 均为偶数，$1 \le x_i, y_i \le N+i-1$，对于所有 $i = 1, 2, \dots, N-1$，所有的 $x_i$ 和 $y_i$ 互不相同。

样例

输入 1

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

输出 1

36
4
0
12
4

输入 2

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

输出 2

4
12
24
0
16
0

输入 3

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

输出 3

16
4
36
16
84
28
0

说明

第一个样例的解释： 最后一次合并如下图所示：