题目描述

<给定一棵n个点的树，树上每条边的长度都为 $1$，第 $i$ 个点的权值为 $a_i$ 。 $Byteasar$ 想要走遍这整棵树，他会按照某个1到n的全排列 $b$ 走 $n-1$ 次，第 $i$ 次他会从 $b_i$ 点走到 $b_{i+1}$ 点，并且这一次的步伐大小为$c_i$。
对于一次行走，假设起点为 $x$ ，终点为 $y$，步伐为 $k$，那么 $Byteasar$ 会从 $x$ 开始，每步往前走 $k$ 步，如果最后不足 $k$ 步就能到达 $y$，那么他会一步走到 $y$。
请帮助 $Byteasar$ 统计出每一次行走时经过的所有点的权值和。

输入格式

第一行包含一个正整数 $n(2<=n<=50000)$。表示节点的个数。
第二行包含 $n$ 个正整数，其中第 $i$ 个数为$a_i(1<=a_i<=10000)$ ，分别表示每个点的权值。
接下来 $n-1$ 行，每行包含两个正整数$u,v(1<=u,v<=n)$，表示 $u$ 与 $v$ 之间有一条边。
接下来一行包含 $n$ 个互不相同的正整数，其中第 $i$ 个数为 $b_i(1<=b_i<=n)$，表示行走路线。
接下来一行包含 $n-1$ 个正整数，其中第 $i$ 个数为$c_i(1<=c_i<n)$，表示每次行走的步伐大小。

输出格式

包含 $n-1$ 行，每行一个正整数，依次输出每次行走时经过的所有点的权值和

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

10
6
10
5