题目描述

给定两棵树 $T_1,T_2$ 和一个长度为 $N$ 的数列

两棵树均包含 $N$ 个顶点，顶点编号为 $1,2,\ldots,N$，并且两棵树的根节点都是顶点 $1$。

对于每个顶点 $i$：

• 设 $P_i$ 为树 $T_1$ 中以 $i$ 为根的子树所包含的顶点编号集合；
• 设 $Q_i$ 为树 $T_2$ 中以 $i$ 为根的子树所包含的顶点编号集合。

定义

请计算 $m_1,m_2,\ldots,m_N$。

输入格式

第一行包含整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

接下来 $N-1$ 行，每行包含两个整数 $u,v$，表示树 $T_1$ 中的一条边。

随后再有 $N-1$ 行，每行包含两个整数 $u,v$，表示树 $T_2$ 中的一条边。

所有边均满足

保证 $T_1$ 和 $T_2$ 均为树。

输出格式

输出 $N$ 行，第 $i$ 行输出 $m_i$。

样例

输入

6
7 10 5 14 8 100
4 5
1 5
5 6
1 2
3 6
1 4
2 4
1 5
3 6
4 6

输出

100
10
5
14
8
100