Description

吉丽YY了一道神题，题面是这样的： “一棵n个点的树，每条边长度为1，第i个结点居住着a[i]个人。假设在i结点举行会议，所有人都从原住址沿着最短路径来到i结点，行走的总路程为b[i]。输出所有b[i]。” 吉丽已经造好了数据，但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗？

Format

Input

第一行一个整数n(2<=n<=300000)。 接下来n-1行，每行两个整数x,y，表示x和y之间有连边。 接下来一行由空格隔开的n个整数bi。

Output

输出一行由空格隔开的n个整数a[i]。 如果你觉得有多组解就任意输出其中一组。

Samples

2
1 2
17 31

31 17

Limitation