Description

给定一棵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统计出每一次行走时经过的所有点的权值和。

Input

第一行包含一个正整数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)，表示每次行走的步伐大小。

Output

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

Sample Input

Sample Output

Hint

鸣谢Claris

Source