Чтобы победить Акселератора, Сёстры Мисаки объединяются! Они займут позиции у ветрогенераторов Академгородка, чтобы ослабить способности Акселератора.

В Академгородке есть $n$ ветрогенераторов, и у Сёстер Мисаки также ровно $n$ человек. Сеть Мисаки представляет собой дерево. Каждый ветрогенератор имеет мощность $w_i$. Когда Акселератор появляется в месте расположения $i$-й сестры, все Сёстры направляют на него свои способности. Однако способности Сёстер могут быть активированы только совместно: каждая пара Сёстер объединяется, чтобы создать энергию для противостояния Акселератору. Если считать местоположение Акселератора корнем дерева, то энергия, вырабатываемая парой сестер $u < v$, равна $w_{\mathrm{lca}(u, v)}$. Общая энергия, вырабатываемая сетью Мисаки, — это сумма энергий всех пар сестер. Вам необходимо для каждого возможного местоположения Акселератора вычислить общую энергию, вырабатываемую сетью Мисаки.

Входные данные

В первой строке дано одно целое число $n$ — количество ветрогенераторов.

Во второй строке даны $n$ целых чисел, где $i$-е число $w_i$ обозначает мощность $i$-го ветрогенератора.

В следующих $n - 1$ строках даны по два целых числа $u$ и $v$ ($1 \le u, v \le n$), обозначающих наличие ребра между $u$ и $v$.

Выходные данные

Выведите одну строку, содержащую $n$ целых чисел, где $i$-е число — это общая энергия, вырабатываемая Сёстрами, если Акселератор находится в позиции $i$.

Подзадачи

Для тестовых случаев 1–4: $n \le 50$

Для тестовых случаев 5–8: $n \le 500$

Для тестовых случаев 9–12: $n \le 2000$

Для тестовых случаев 13–14: $n \le 5 \times 10^4$, дерево является бинарным

Для тестовых случаев 15–16: $n \le 5 \times 10^4$, дерево является цепью

Для тестовых случаев 17–18: $n \le 5 \times 10^4$

Для тестовых случаев 19–20: $n \le 5 \times 10^5$, дерево является цепью

Для тестовых случаев 21–22: $n \le 5 \times 10^5$, дерево является звездой

Для тестовых случаев 23–25: $n \le 5 \times 10^5$

Для $100\%$ данных гарантируется, что $n \le 5 \times 10^5, 0 \le w_i \le 10^6$.

Примеры

Пример 1

Входные данные

3
2 5 7
3 2
1 2

Выходные данные

9 15 19