Bajtazar przygotowuje właśnie zadanie na konkurs programistyczny. Napisał już szkic treści:

W Bajtocji jest $n$ miast połączonych $n$ - 1 dwukierunkowymi drogami w taki sposób, że korzystając z sieci drogowej da się przejechać pomiędzy dowolnymi dwoma miastami. Przebycie drogi łączącej dwa bezpośrednio połączone miasta zajmuje jedną godzinę. Miasta są ponumerowane od 1 do $n$. W mieście $i$ mieszka $a_{i}$ mieszkańców.

W przyszłym roku w Bajtocji mają się odbyć wybory. Aby mieć pełną kontrolę nad przebiegiem głosowania, król Bajtocji postanowił, że głosowanie zostanie zorganizowane w tylko jednym mieście. Wszyscy mieszkańcy Bajtocji udadzą się najkrótszą drogą do miasta z urną wyborczą i tam oddadzą głos. Teraz pozostało wybrać miasto, w którym odbędzie się głosowanie. Wybór ten zależy od wielu czynników. W szczególności, dla każdego miasta $i$ chcielibyśmy obliczyć łączny czas potrzebny wszystkim mieszkańcom Bajtocji na dotarcie do miasta $i$ (oznaczmy tę wartość przez $b_{i}$) [...]

Bajtazar miał już przygotowane wyjątkowo trudne testy do zadania, jednak przypadkiem stracił połowę danych. Teraz z każdego testu pozostały mu tylko opisy połączeń drogowych i pliki wyjściowe zawierające wartości $b_{i}$. Na tej podstawie chciałby odtworzyć liczbę mieszkańców każdego miasta Bajtocji.

Input Format

W pierwszym wierszu wejścia znajduje się liczba całkowita $n$ ($2 \le n \le 300\,000$) oznaczająca liczbę miast w Bajtocji. Każdy z kolejnych $n$ - 1 wierszy zawiera opis jednego połączenia drogowego w postaci pary liczb całkowitych $x_{i}$, $y_{i}$ (1 ≤ $x_{i}$, $y_{i}$ ≤ $n$). Oznaczają one, że miasta $x_{i}$ oraz $y_{i}$ są połączone drogą.

Kolejny wiersz zawiera ciąg $n$ liczb całkowitych $b_{i}$ ($0 \le b_{i} \le 10^{9}$).

Output Format

Wypisz jeden wiersz z ciągiem $n$ liczb całkowitych $a_{i}$. Liczba $a_{i}$ powinna oznaczać liczbę mieszkańców miasta Bajtocji numer $i$. Dla podanego ciągu $a_{i}$, po rozwiązaniu zadania Bajtazara powinno się otrzymać ciąg $b_{i}$ podany na wejściu.

Dane wejściowe są tak dobrane, że odpowiedź zawsze istnieje. Jeśli istnieje wiele poprawnych odpowiedzi, Twój program może wypisać dowolną z nich.

Examples

Input

2
1 2
17 31

Output

31 17