시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB343311.538%

문제

Zadano je $N$ kvadrata koji su označeni brojevima od $1$ do $N$. Kvadrat s oznakom $i$ ima duljinu stranice $a_i$, gdje je $a_i$ neki paran broj. Na početku je svaki kvadrat obojan u crnu boju.

Jura kod sebe ima koordinatni sustav $i$ odlučio je iskoristiti $N - 1$ sekundi svog života da bi se malo pozabavio sa zadanim kvadratima. U $i$-toj sekundi Jura je uzeo kvadrate s oznakama $x_i$ i $y_i$ te ih spojio u novi kvadrat s oznakom $n + i$ (nakon spajanja kvadrati s oznakama $x_i$ i $y_i$ više ne postoje).

Prilikom spajanja dva kvadrata, Jura ih postavi u koordinatni sustav tako da su im središta u koordinatama $(0, 0)$ te da su im stranice paralelne s osima. Novi kvadrat bit će dimenzija kao veći od dva koja se spajaju, a bit će obojan na sljedeći način: ako je neka točka u oba kvadrata crna ili u oba bijela, u novom kvadratu bit će bijela, a inače će biti crna.

Spajanja, naravno, nisu besplatna, cijena spajanja jednaka je površini svih točaka koje su crne u oba kvadrata istovremeno. Juru zanima kolika je cijena svakog od $N - 1$ spajanja koje je napravio. Slike prikazuju primjere spajanja.

입력

U prvom je retku prirodni broj $N$, broj kvadrata.

U drugom je retku niz prirodnih brojeva $a_1, a_2, \dots , a_N$ koji predstavlja duljine stranica zadanih kvadrata.

U sljedećih $N - 1$ redaka nalaze se po $2$ broja, u $i$-tom od tih $N - 1$ redaka nalaze se brojevi $x_i$ i $y_i$, oznake kvadrata koje je Jura spojio u $i$-toj sekundi.

출력

Ispišite $N - 1$ redaka. U $i$-tom retku ispišite po jedan broj, cijenu $i$-tog spajanja.

서브태스크

U svim podzadacima vrijedi $1 ≤ N ≤ 10^5$, $2 ≤ a_i ≤ 10^6$, ai je paran za sve $i = 1, 2, \dots , N$, $1 ≤ x_i , y_i ≤ N + i - 1$, za sve $i = 1, 2, \dots , N - 1$, svi $x_i$ i $y_i$ međusobno su različiti.

번호배점제한
114

$N ≤ 5000$

225

$x_1 = 1$, $y_1 = 2$, $x_i = i + 1$, $y_i = N + i - 1$ za sve $i = 2, 3, \dots , N-1$

317

$N$ je potencija broja $2$, $x_i = 2i - 1$, $y_i = 2i$

421

$N ≤ 30000$

523

Nema dodatnih ograničenja.

예제 입력 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

힌트

Pojašnjenje prvog probnog primjera:

Posljednje spajanje prikazano je na slici:

채점 및 기타 정보

  • 예제는 채점하지 않는다.