W Królestwie JOI jest $N$ miast, ponumerowanych od $1$ do $N$. Miasto $1$ jest stolicą. Każde miasto ma wartość zwaną żywotnością, a początkowa żywotność miasta $i$ ($1\le i\le N$) wynosi $C_i$.

Droga w Królestwie JOI łączy dwa różne miasta w obu kierunkach. Początkowo w Królestwie JOI nie ma żadnych dróg. Zaplanowałeś budowę $N-1$ dróg. $j$-ta budowa ($1\le j\le N-1$) ma przebiegać następująco.

• Wyznaczane są dwa miasta, $A_j$ i $B_j$, takie że po drogach zbudowanych do tej chwili można dotrzeć z miasta $1$ do miasta $A_j$, ale nie można dotrzeć z miasta $1$ do miasta $B_j$.
• Budujesz drogę łączącą miasta $A_j$ i $B_j$. Koszt tej budowy jest równy liczbie par miast $(s,t)$ spełniających następujące warunki:

Miasta $s$ i $t$ leżą na najkrótszej ścieżce między miastem $1$ a miastem $A_j$; podróżując z miasta $1$ do miasta $A_j$, dociera się do miasta $s$ przed miastem $t$; żywotność miasta $s$ jest ściśle większa od żywotności miasta $t$.

Do miast leżących na ścieżce między miastem $1$ a miastem $A_j$ zaliczamy również miasta $1$ i $A_j$. Zauważ, że najkrótsza ścieżka między miastem $1$ a miastem $A_j$ jest jednoznacznie wyznaczona.

• Żywotność każdego miasta leżącego na ścieżce między miastem $1$ a miastem $A_j$ zmienia się na żywotność miasta $B_j$.

Chcesz poznać koszt każdej budowy.

Zadanie

Mając dane o miastach i budowach dróg, napisz program obliczający koszt każdej budowy.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz wejścia zawiera liczbę całkowitą $N$. Oznacza to, że w Królestwie JOI jest $N$ miast.
• Drugi wiersz wejścia zawiera $N$ liczb całkowitych $C_1,C_2,\ldots,C_N$, oddzielonych spacjami. Oznacza to, że początkowa żywotność miasta $i$ ($1\le i\le N$) wynosi $C_i$.
• $j$-ty z kolejnych $N-1$ wierszy ($1\le j\le N-1$) zawiera dwie liczby całkowite $A_j,B_j$, oddzielone spacją. Oznacza to, że miasta $A_j$ i $B_j$ wyznaczono do $j$-tej budowy drogi.

Wyjście

Wypisz $N-1$ wierszy na standardowe wyjście. $j$-ty wiersz ($1\le j\le N-1$) powinien zawierać koszt $j$-tej budowy drogi.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $1\le N\le 100\,000$.
• $1\le C_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $1\le A_j\le N$ ($1\le j\le N-1$).
• $1\le B_j\le N$ ($1\le j\le N-1$).
• Po drogach zbudowanych przed $j$-tą budową można dotrzeć z miasta $1$ do miasta $A_j$, ale nie można dotrzeć z miasta $1$ do miasta $B_j$ ($1\le j\le N-1$).

Podzadania

Są 3 podzadania. Ich punktacja i dodatkowe ograniczenia są następujące:

Podzadanie 1 [7 punktów]

• $N\le 500$.

Podzadanie 2 [9 punktów]

• $N\le 4000$.

Podzadanie 3 [84 punkty]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

5
1 2 3 4 5
1 2
2 3
2 4
3 5

Wyjście 1

0
0
0
2

Uwagi

W pierwszym przykładzie budowy przebiegają następująco:

• Podczas pierwszej budowy nie ma par $(s,t)$ spełniających warunki, więc koszt wynosi $0$. Powstaje droga łącząca miasta $1$ i $2$, a żywotność miasta $1$ zmienia się na $2$.
• Podczas drugiej budowy również nie ma par $(s,t)$ spełniających warunki, więc koszt wynosi $0$. Powstaje droga łącząca miasta $2$ i $3$, a żywotność miast $1$ i $2$ zmienia się na $3$.
• Podczas trzeciej budowy również nie ma par $(s,t)$ spełniających warunki, więc koszt wynosi $0$. Powstaje droga łącząca miasta $2$ i $4$, a żywotność miast $1$ i $2$ zmienia się na $4$.
• Podczas czwartej budowy dwie pary $(s,t)=(1,3),(2,3)$ spełniają warunki, więc koszt wynosi $2$. Powstaje droga łącząca miasta $3$ i $5$, a żywotność miast $1$, $2$ i $3$ zmienia się na $5$.

Wejście 2

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

Wyjście 2

0
0
0
1
1
0
1
2
3