Страна R состоит из n городов и n - 1 двусторонних дорог, расположенных так, что из любого города можно добраться до любого другого. Президент этой страны решил выбрать столицу. Как только столица будет выбрана, все жители страны съедутся на парад в столицу. Известно, что в i-м городе проживает vi жителей. Решение, какой же именно город станет столицей, еще не принято, так как еще не до конца понятно, что же для страны будет выгоднее: с одной стороны, можно неплохо простимулировать транспортную систему страны, если сделать столицу в достаточно удаленном и малонаселенном городе, а с другой стороны, столица, расположенная в крупном городе поближе к центру, будет быстро развиваться и тоже потянет экономику вверх. Поэтому президент хочет посчитать для каждого города i, сколько суммарно дорог преодолеют все жители страны, чтоб добраться до столицы, если сделать ее в городе i. Без сомнения, обладая этой информацией, он примет правильное решение и приведет страну к успеху и процветанию.
В первой строке записано целое число n (1 ≤ n ≤ 100000) — количество городов в стране.
В следующей строке записаны n чисел vi (1 ≤ vi ≤ 108) — количества жителей в каждом городе.
В каждой из следующих n - 1 строк записаны два числа ai и bi (1 ≤ ai, bi ≤ n) — номера городов соединенных дорогой.
Выведите n чисел. i-е число должно равняться суммарно пройденному расстоянию всех жителей страны до города i.
## Входные Данные
В первой строке записано целое число n (1 ≤ n ≤ 100000) — количество городов в стране.В следующей строке записаны n чисел vi (1 ≤ vi ≤ 108) — количества жителей в каждом городе.В каждой из следующих n - 1 строк записаны два числа ai и bi (1 ≤ ai, bi ≤ n) — номера городов соединенных дорогой.
## Выходные Данные
Выведите n чисел. i-е число должно равняться суммарно пройденному расстоянию всех жителей страны до города i.
## Пример
Входные данные57 3 2 5 41 21 33 43 5Выходные данные23 38 22 33 35
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of cities.
Let $ v_i \in \mathbb{Z}^+ $ be the population of city $ i $, for $ i \in \{1, \dots, n\} $.
Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, \dots, n\} $ and edge set $ E $ of size $ n-1 $, representing the road network.
**Constraints**
1. $ 1 \leq n \leq 100000 $
2. $ 1 \leq v_i \leq 10^8 $ for all $ i \in \{1, \dots, n\} $
3. Each edge $ (a_i, b_i) \in E $ connects two distinct cities.
**Objective**
For each city $ i \in \{1, \dots, n\} $, compute:
$$
S_i = \sum_{j=1}^{n} v_j \cdot d(j, i)
$$
where $ d(j, i) $ is the shortest path distance (number of edges) between cities $ j $ and $ i $ in tree $ T $.