给定两棵树 $t_1$ 和 $t_2$。每棵树包含 $N$ 个顶点。在每棵树中，顶点编号从 $1$ 到 $N$，且根节点均为顶点 $1$。

令 $p_i$ 和 $q_i$ 分别为树 $t_1$ 和 $t_2$ 中以顶点 $i$ 为根的子树所包含的顶点编号集合。

同时给定一个整数序列 $a_1, a_2, \dots, a_N$。

定义 $m_i = \max\{a_k \mid k \in p_i \cap q_i\}$。

编写程序计算 $m_1, m_2, \dots, m_N$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 250\,000$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

接下来 $n-1$ 行描述树 $t_1$ 的边，每行包含两个由边连接的顶点编号 $u$ 和 $v$ ($1 \le u, v \le n; u \neq v$)。

接下来 $n-1$ 行描述树 $t_2$ 的边，每行包含两个由边连接的顶点编号 $u$ 和 $v$ ($1 \le u, v \le n; u \neq v$)。

保证 $t_1$ 和 $t_2$ 均为树。

输出格式

输出 $n$ 行，每行包含一个数字 $m_i$，依次对应 $m_1, m_2, \dots, m_n$。

样例

输入 1

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

输出 1

100
10
5
14
8
100