Byteasar 是一个了不起的人——在过去的 21 年里，他当过邮递员、银行家、滑冰运动员，甚至还当过国王！难怪他有很多朋友。或者说曾经有很多朋友，因为他频繁更换职业和工作地点，不幸使他与许多老朋友失去了联系。现在是时候改变这一切了！Byteasar 即将开启一场 Byteotia 的环游之旅，以重温旧情。

Byteotia 有 $n$ 个城镇，由 $n-1$ 条双向道路连接。我们的主角想要访问每一个城镇，并且已经确定了访问顺序。从一个城镇到行程中的下一个城镇，他将驾驶从 BMW（Byteotian Motor Wagons）租来的汽车。租车是完全免费的，但汽车必须加油——油箱容量为 $k$ 的汽车必须在最开始加满油，之后每行驶 $k$ 条道路后必须重新加油。BMW 非常清楚 Byteasar 的计划以及他打算尽快完成旅程的事实。因此，他们巧妙地选择了租赁汽车的油箱容量，使得在每个城镇，Byteasar 都必须为两辆车（重新）加油：他到达时驾驶的那辆和离开时驾驶的那辆（初始城镇和最终城镇除外，那里只需要为一辆车加油）。

已知 Byteasar 的行程、燃油价格和油箱容量，请确定行程中每一段路程的加油成本。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 50\,000$)，表示 Byteotia 的城镇数量。城镇编号从 $1$ 到 $n$。下一行包含一个由 $n$ 个整数 $c_1, \dots, c_n$ ($1 \le c_i \le 10\,000$) 组成的序列，用空格分隔，表示 Byteotia 所有城镇的燃油价格：数字 $c_i$ 是在 $i$ 号城镇加满任何汽车油箱的成本（这是“自助加油”，即“只需 $c_i$ 即可加满油”）。

接下来的 $n-1$ 行描述了 Byteotia 的道路网络。每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n$)，用空格分隔，表示 $a$ 号城镇和 $b$ 号城镇之间有一条双向道路。

随后是一行包含 $n$ 个整数 $t_1, \dots, t_n$ 的序列，用空格分隔，指定了 Byteasar 访问城镇的顺序（$1$ 到 $n$ 的每个数字在序列中恰好出现一次）。最后，输入的最后一行包含一个由 $n-1$ 个整数 $k_1, \dots, k_{n-1}$ 组成的序列，用空格分隔，指定了租赁汽车的油箱容量：数字 $k_i$ 表示在从 $t_i$ 号城镇前往 $t_{i+1}$ 号城镇的途中，Byteasar 每行驶 $k_i$ 条道路后必须加油。你可以假设 $k_i$ 总是能整除这两个城镇之间的距离。

在总分 36% 的测试中，满足条件 $n \le 10\,000$。此外，在其中占总分 28% 的子任务中，满足更强的条件 $n \le 1000$。

输出格式

你的程序应向标准输出打印 $n-1$ 行，每行包含一个整数。第 $i$ 行的数字应为从 $t_i$ 号城镇前往 $t_{i+1}$ 号城镇途中加油的总成本。

样例

输入 1

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

输出 1

10
6
10
5