该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵有 $n$ 结点的有根树 $T$，结点依次以 $1,2,\ldots,n$ 编号，根结点编号为 $1$。方便起见，编号为 $i$ 的结点称为结点 $i$。

另外，每个结点还有一个正整数点权，其中结点 $i$ 的点权为 $v_i$。

对于每个 $1\le x\le n$，我们定义结点 $x$ 的 GPA（Greatest Prime Ancestor）为 $x$ 的所有祖先（不包括自身）中，点权是素数的前提下的最大点权。

你需要计算每个结点的 GPA，如果对应结点的 GPA 不存在则输出 $-1$。

输入格式

第一行，一个正整数 $n$，表示结点数量。

第二行，一行 $n$ 个正整数 $v_1,v_2,\ldots,v_n$，表示每个结点的点权。

之后有 $n-1$ 行，每行有两个正整数 $p,q$，表示树上连接结点 $p,q$ 的一条边。保证 $1\leq p,q\leq n$。

输出格式

输出一行 $n$ 个整数，其中第 $i$ 个整数表示结点 $i$ 的 GPA。如果结点 $i$ 的 GPA 不存在，则输出的第 $i$ 个整数为 $-1$。

6
60 11 18 1 19 13
1 6
2 3
2 6
4 5
5 6

-1 13 13 19 13 -1

5
2 17 13 100 5
1 2
3 4
2 3
5 4

-1 2 17 17 17

3
1 2 3
1 2
2 3

-1 -1 2

提示

【样例 1 解释】

如图所示，黑色数字为结点编号，蓝色数字为点权。

以计算结点 $3$ 的 GPA 为例，其祖先点权有 $11,13,60$，其中的素数有 $11,13$，最大的是 $13$。

【数据规模与约定】

对于全部数据，保证 $1\le n\le 5\times 10^5$，$1\le v_i\le 10^7$。

本题共 $10$ 个测试点，每个 $10$ 分。其中，部分测试点具有特殊性质，具体参考下表：

• 特殊性质 A（一条链）：保证每条边连接的结点编号都是相邻两自然数，例如样例 2。
• 特殊性质 B：保证任意结点到根的距离不超过 $50$。