Bajtazar正在为一个编程竞赛准备一道题目。他已经写好了题目草稿：

在巴伊托奇亚有 $n$ 座城市，由 $n$ - 1 条双向道路连接，使得通过道路网络可以在任意两座城市之间通行。走完连接两个直接相连城市的道路需要一小时。城市编号从1到 $n$。在城市 $i$ 居住着 $a_{i}$ 名居民。

明年巴伊托奇亚将举行选举。为了完全控制投票过程，巴伊托奇亚国王决定只在一个城市组织投票。所有巴伊托奇亚居民都将沿着最短路径前往设有投票箱的城市并进行投票。现在需要选择一个城市作为投票地点。这个选择取决于许多因素。特别是，对于每个城市 $i$，我们希望计算所有巴伊托奇亚居民到达城市 $i$ 所需的总时间（我们将此值记为 $b_{i}$）[...]

Bajtazar已经为这道题准备了非常难的测试数据，但意外地丢失了一半数据。现在每个测试只剩下道路连接的描述和包含 $b_{i}$ 值的输出文件。基于此，他想恢复巴伊托奇亚每个城市的居民数量。

Input Format

输入的第一行包含一个整数 $n$ ($2 \le n \le 300\,000$)，表示巴伊托奇亚的城市数量。接下来的 $n$ - 1 行每行包含一个道路连接的描述，形式为一对整数 $x_{i}$，$y_{i}$ ($1 \le x_{i}, y_{i} \le n$)。它们表示城市 $x_{i}$ 和 $y_{i}$ 之间有一条道路连接。

下一行包含 $n$ 个整数 $b_{i}$ ($0 \le b_{i} \le 10^{9}$) 的序列。

Output Format

输出一行，包含 $n$ 个整数 $a_{i}$ 的序列。数字 $a_{i}$ 应表示巴伊托奇亚第 $i$ 个城市的居民数量。对于给定的 $a_{i}$ 序列，在解决了Bajtazar的问题后，应该得到输入中给出的 $b_{i}$ 序列。

输入数据经过精心选择，因此答案总是存在的。如果存在多个正确答案，你的程序可以输出其中任意一个。

Examples

Input

2
1 2
17 31

Output

31 17