题目描述

在一片树林中，有$n$个树洞，按顺序从1到$n$编号，每个树洞里住着至少一只松鼠。

一条藤蔓连接两个树洞，共有$n$-1条藤蔓，使得任意两个树洞可以直接或间接到达。

这些小松鼠经常举办聚会，当某个树洞中的小松鼠举办聚会时，它们也会邀请距离自家树洞不超过$k$条藤蔓范围的邻居们前来参加聚会。

请计算出每个树洞分别在举办聚会时，最多有多少只小松鼠参加聚会，并按照树洞编号从1到$n$依次输出结果。

例如:$n$ = 4，表示有4个树洞，1到4号树洞中居住的小松鼠的数量分别为:5、3、6、1；共有3条藤蔓，每条藤蔓连接两个树洞，分别为:1和2、1和 3、2和 4; $k$ = 2，表示当某个树洞中的小松鼠举办聚会时，它们会邀请距离自家树洞不超过2条藤蔓范围的邻居们前来参加聚会。

根据上图得知: 当1号树洞的小松鼠举办聚会时，1、2、3、4号树洞中的小松鼠可以参加，最多会有15(5+3+6+1)只小松鼠参加;

当2号树洞的小松鼠举办聚会时，1、2、3、4号树洞中的小松鼠可以参加，最多会有15(5+3+6+1)只小松鼠参加；

当3号树洞的小松鼠举办聚会时，1、2、3号树洞中的小松鼠可以参加，最多会有14(5+3+6)只小松鼠参加;

当4号树洞的小松鼠举办聚会时，1、2、4号树洞中的小松鼠可以参加，最多会有9(5+3+1)只小松鼠参加。

故答案为: 15 15 14 9

输入规则

第一行输入一个整数 $n (1 \le n \le 10000)$，表示树洞的数量 接下来 $n$ 行，每行输入一个整数 $C_i(1 \le C_i \le 1000)$，表示每个树洞中居住的小松鼠的数量 接下来 $n$ 行，每行输入两个整数 $a_i,b_i(1 \le a_i,b_i \le n)$，表示藤蔓连接两个树洞的编号，整数之间以一个空格隔开 最后一行输入一个整数 $k(1 \le k \le 20)$，表示邀请邻居的距离限制

输出规则

共 $n$ 行，每行输出一个整数，表示每个树洞中的小松鼠在举办聚会时，参加聚会的小松鼠的最大数量，按照树洞编号从 $1$ 到 $n$ 依次输出结果。

样例

输入样例 #1

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

输出样例 #1

15
15 
15
9