给出一棵有 $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$。
## Input
第一行一个整数 $n$，表示有 $n$ 个节点。
第二行 $n$ 个正整数，表示 $a_1,a_2\dots a_n$。
接下来 $n-1$ 行，每行两个正整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间有一条边。
## Output
输出共 $n$ 行，每行一个整数。
第 $i$ 行表示 $b_i$ 对 $998244353$ 取模后的结果。
[samples]
## Background
>$$你是天使，$$
>
>$$于光与圣歌中降临。$$
>
>$$我是恶魔，$$
>
>$$从血与污泥中爬出。$$
>
>$$我想拥抱你，$$
>
>$$但是害怕血，$$
>
>$$染红你洁白的羽翼。$$
## Note
#### 【样例解释】
建出的树如图。
有以下贡献：
- 对 $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 捆绑测试，只有通过一个子任务的全部测试点才能获得此子任务的分数。**