悲哀（Sorrow）

>$$你是天使，$$ > >$$于光与圣歌中降临。$$ > >$$我是恶魔，$$ > >$$从血与污泥中爬出。$$ > >$$我想拥抱你，$$ > >$$但是害怕血，$$ > >$$染红你洁白的羽翼。$$

给出一棵有 $n$ 个节点且以 $1$ 为根节点的树，每个节点有两个权值 $a_i,b_i$（$1\le i\le n$）。$a_i$ 已经给出，$b_i$ 初始为 $0$。 现在对于每一对节点 $(u,v)$（$1\le u<v\le n$），设 $x=\operatorname{LCA}(u,v)$，如果 $\gcd(a_u,a_v)>1$ 那么 $b_x\gets b_x+a_u\times a_v$，否则不做任何操作。 对于每个 $1\le i\le n$ 求出 $b_i\bmod998244353$。

第一行一个整数 $n$，表示有 $n$ 个节点。 第二行 $n$ 个正整数，表示 $a_1,a_2\dots a_n$。 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

输出共 $n$ 行，每行一个整数。 第 $i$ 行表示 $b_i$ 对 $998244353$ 取模后的结果。

8
3 7 2 2 2 3 72 24 
1 2
1 3
1 4
4 5
2 6
5 7
4 8

785
0
0
1972
144
0
0
0

15
73 83 31 9514 1189 43 79 2 2 1798 5063 2 5 2573 53 
1 2
2 3
1 4
4 5
1 6
3 7
5 8
5 9
6 10
7 11
10 12
9 13
7 14
13 15

23952214
633788
79763
38056
4
0
13027099
0
0
3596
0
0
0
0
0

#### 【样例解释】  建出的树如图。 有以下贡献： - 对 $1$ 号节点： $(3,4)$ 贡献 $4$。 $(3,5)$ 贡献 $4$。 $(3,7)$ 贡献 $144$。 $(3,8)$ 贡献 $48$。 $(1,6)$ 贡献 $9$。 $(1,7)$ 贡献 $216$。 $(1,8)$ 贡献 $72$。 $(6,7)$ 贡献 $216$。 $(6,8)$ 贡献 $72$。 总共 $785$。 - 对 $4$ 号节点： $(4,5)$ 贡献 $4$。 $(4,7)$ 贡献 $144$。 $(4,8)$ 贡献 $48$。 $(5,8)$ 贡献 $48$。 $(7,8)$ 贡献 $1728$。 总共 $1972$。 - 对 $5$ 号节点： $(5,7)$ 贡献 $144$。 总共 $144$。 其他节点显然都为 $0$。 #### 【数据范围】 | subtask 编号 | $n$ | $a_i$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $100$ | $\le 1000$ | $-$ | $5$ | | $1$ | $2000$ | $\le 10^5$ | $-$ | $10$ | | $2$ | $10^5$ | $\le 5 \times 10^5$ | $A$ | $25$ | | $3$ | $2 \times 10^5$ | $\le 5 \times 10^5$ | $B$ | $30$ | | $4$ | $2 \times 10^5$ | $\le 5 \times 10^5$ | $-$ | $30$ | 特殊性质 $A$：保证所有的 $a_i$ 随机生成。 特殊性质 $B$：保证树的形态是一棵完全二叉树。 对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$1\le a_i\le5\times10^5$。 **特别提醒：本题使用 subtask 捆绑测试，只有通过一个子任务的全部测试点才能获得此子任务的分数。**