Description

给定一棵$n$个点以$1$为根的树，每个点有点权，输出每个子树的子树和。

Format

Input

第一行一个整数$n(1 \leq n \leq 10^5)$，其含义见题目描述。

接下来1行，$n$个整数，其中第$i$个数代表第$i$个点的点权（不超过100的非负整数）。

接下来$n-1$行，每行两个整数$x(1\leq x \leq n)$和$y(1 \leq y \leq n)$，代表$x$和$y$之间有一条边。

Output

一行，$n$个整数，其中第$i$个数代表以$i$为根的子树的子树和。

Samples

6
1 2 3 4 5 6
1 2
1 3
4 1
5 3
3 6

21 2 14 4 5 6

Limitation

**