Aby pokonać Acceleratora, Siostry Misaka muszą połączyć siły! Będą one stacjonować przy turbinach wiatrowych w Mieście Akademii, aby osłabić zdolności Acceleratora.

W Mieście Akademii znajduje się $n$ turbin wiatrowych, a Sióstr Misaka jest dokładnie $n$. Połączenia sieci Misaka tworzą drzewo. Każda turbina wiatrowa ma moc $w_i$. Gdy Accelerator pojawi się w miejscu, w którym znajduje się $i$-ta Siostra Misaka, wszystkie Siostry użyją swoich zdolności w jego stronę. Zdolności Sióstr Misaka można aktywować tylko wspólnie; każda para Sióstr łączy się, aby wytworzyć energię przeciwko Acceleratorowi. Jeśli przyjmiemy pozycję Acceleratora za korzeń drzewa, to energia wytworzona przez parę sióstr $u < v$ wynosi $w_{\mathrm{lca}(u, v)}$. Całkowita energia wytworzona przez sieć Misaka to suma energii wszystkich par sióstr. Twoim zadaniem jest obliczenie całkowitej energii wytworzonej przez sieć Misaka dla każdej możliwej pozycji Acceleratora.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $n$ oznaczającą liczbę turbin wiatrowych.

Druga linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba $w_i$ oznacza moc $i$-tej turbiny wiatrowej.

Kolejne $n - 1$ linii zawiera po dwie liczby całkowite $u\ v$, gdzie $1 \le u, v \le n$, oznaczające krawędź między $u$ a $v$.

Wyjście

Wypisz w jednej linii $n$ liczb całkowitych, gdzie $i$-ta liczba oznacza całkowitą energię wytworzoną przez Siostry, jeśli Accelerator znajduje się w pozycji $i$.

Przykład

Przykład 1

Wejście

3
2 5 7
3 2
1 2

Wyjście

9 15 19

Podzadania

Dla testów 1-4: $n \le 50$

Dla testów 5-8: $n \le 500$

Dla testów 9-12: $n \le 2000$

Dla testów 13-14: $n \le 5\times 10^4$, drzewo jest drzewem binarnym

Dla testów 15-16: $n \le 5\times 10^4$, drzewo jest ścieżką

Dla testów 17-18: $n \le 5\times 10^4$

Dla testów 19-20: $n \le 5\times 10^5$, drzewo jest ścieżką

Dla testów 21-22: $n \le 5\times 10^5$, drzewo jest gwiazdą

Dla testów 23-25: $n \le 5\times 10^5$

Dla $100\%$ danych wejściowych: $n \le 5\times 10^5, 0 \le w_i \le 10^6$