题目描述

小 Y 有一棵以 $1$ 号节点为根的树，共 $n$ 个节点，每个节点被涂上了某种颜色，第 $i$ 个节点的颜色为 $a_i$。

对每个节点 $u$，请你求出：在 $u$ 的子树中，是否存在一种颜色，它出现的次数严格大于子树大小的一半。若存在，输出这种颜色的编号；否则输出 -1。

可以证明，满足条件的颜色至多只有一种。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1\sim a_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条边。

输出格式

共 $n$ 行，第 $u$ 行表示节点 $u$ 的答案。

输入输出样例 #1

输入 #1

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

输出 #1

2
2
2
2
3

说明

【样例解释】

节点 $1$ 的子树包含全部 $5$ 个节点，颜色 $2$ 出现 $3$ 次，$3>5/2$，故答案为 $2$。

节点 $2$ 的子树为 $\{2,4,5\}$，颜色 $2$ 出现 $2$ 次，$2>3/2$，故答案为 $2$。

节点 $3,4,5$ 的子树都只含自己，颜色出现 $1$ 次，$1>1/2$，故答案为各自的颜色。

【数据范围】

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le a_i\le 10^9$。