题目北京

Banana 的爱好是种树，尤其喜欢种香蕉树~

题目描述

Banana 的香蕉树由 $n$ 个分叉点和 $n-1$ 条树枝组成，可以看作是一个 $n$ 个点 $n-1$ 条边的无向连通图。

Banana 花园的土地很神奇，富含有极高的营养成分，这些营养会被树根吸收，然后沿着树枝传递到各个分叉点。但是营养在传递过程中会损耗。具体的，令 $rt$ 为根节点，$d(x,y)$ 表示 $x$ 到 $y$ 要经过的树枝数，则分叉点 $x$ 会获得 $C-d(rt,x)$ 点营养。

在丰富营养的滋养下，每天树上都会长满香蕉。假设分叉点 $i$ 获得了 $c_i$ 点营养，则这个点上会长 $a_i\times c_i$ 根香蕉。

现在 Banana 想知道每天树上总共会长多少根香蕉。然而由于香蕉树太大了，Banana 不知道那个是根，所以他想知道对于每个 $i\in [1,n]$，如果分叉点 $i$ 是根的话，一天会长多少根香蕉？

输入格式

第一行两个整数 $n,C$。

第二行 $n$ 个整数，第 $i$ 个数是 $a_i$。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示一条连接分叉点 $x$ 和 $y$ 的树枝。数据保证所有树枝会形成一棵树。

输出格式

共 $n$ 行，第 $i$ 行表示以分叉点 $i$ 为根时一天长的香蕉数。

样例

输入样例 #1

4 4
1 2 3 4
1 2
1 3
2 4

输出样例 #1

27
29
23
27

数据范围

$1\leq n\leq 10^5$，$n\leq C\leq 10^6$，$0\leq a_i\leq 10^7$