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

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.

입력 형식

W pierwszym wierszu wejścia znajduje się liczba całkowita n (2 ≤ n ≤ 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ą.</p>

Kolejny wiersz zawiera ciąg n liczb całkowitych b_i (0 ≤ b_i ≤ 10⁹).

출력 형식

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.</p>

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.

예제 입력

2
1 2
17 31

예제 출력

31 17