题目描述

吉丽$\text{YY}$了一道神题，题面是这样的：

“一棵$n$个点的树，每条边长度为$1$，第$i$个结点居住着$a[i]$个人。假设在i结点举行会议，所有人都从原住址沿着最短路径来到i结点，行走的总路程为$b[i]$。输出所有$b[i]$。”

吉丽已经造好了数据，但熊孩子把输入文件中所有$a[i]$给删掉了。你能帮他恢复吗？

输入格式

第一行一个整数$n$。

接下来$n-1$行，每行两个整数$x,y$，表示$x$和$y$之间有连边。 接下来一行由空格隔开的$n$个整数$b[i]$。

输出格式

输出一行由空格隔开的$n$个整数$a[i]$。

如果你觉得有多组解就任意输出其中一组。

样例

2
1 2
17 31

31 17

数据规模与约定

对于$100\%$的数据：$2\le n\le 300000,0\le b[i]\le 10^9$.