题目背景

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

题目描述

给出一棵有 $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$		$B$	$30$
$4$			$-$

特殊性质 $A$：保证所有的 $a_i$ 随机生成。

特殊性质 $B$：保证树的形态是一棵完全二叉树。

对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$1\le a_i\le5\times10^5$。

特别提醒：本题使用 subtask 捆绑测试，只有通过一个子任务的全部测试点才能获得此子任务的分数。