Background

$$You are an angel,$$ $$descending amid light and holy hymns.$$ $$I am a demon,$$ $$crawling out of blood and filthy mud.$$ $$I want to hold you,$$ $$but I fear my blood$$ $$will stain your pure white wings red.$$

Problem Description

Given a tree with $n$ nodes rooted at node $1$. Each node has two weights $a_i, b_i$ ($1 \le i \le n$). The values $a_i$ are given, and all $b_i$ are initially $0$.

Now, for every pair of nodes $(u, v)$ ($1 \le u < v \le n$), let $x = \operatorname{LCA}(u, v)$. If $\gcd(a_u, a_v) > 1$, then set $b_x \gets b_x + a_u \times a_v$; otherwise, do nothing.

For each $1 \le i \le n$, output $b_i \bmod 998244353$.

Input Format

The first line contains an integer $n$, meaning there are $n$ nodes.

The second line contains $n$ positive integers, representing $a_1, a_2, \dots, a_n$.

The next $n - 1$ lines each contain two positive integers $u, v$, indicating there is an edge between node $u$ and node $v$.

Output Format

Output $n$ lines, each containing one integer.

The $i$-th line should be the value of $b_i$ modulo $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

Hint

Sample Explanation

The constructed tree is shown in the figure.

The following contributions exist:

• For node $1$:

$(3, 4)$ contributes $4$.

$(3, 5)$ contributes $4$.

$(3, 7)$ contributes $144$.

$(3, 8)$ contributes $48$.

$(1, 6)$ contributes $9$.

$(1, 7)$ contributes $216$.

$(1, 8)$ contributes $72$.

$(6, 7)$ contributes $216$.

$(6, 8)$ contributes $72$.

Total: $785$.

• For node $4$:

$(4, 5)$ contributes $4$.

$(4, 7)$ contributes $144$.

$(4, 8)$ contributes $48$.

$(5, 8)$ contributes $48$.

$(7, 8)$ contributes $1728$.

Total: $1972$.

• For node $5$:

$(5, 7)$ contributes $144$.

Total: $144$.

All other nodes are clearly $0$.

Constraints

Special property $A$: it is guaranteed that all $a_i$ are generated randomly.

Special property $B$: it is guaranteed that the tree is a complete binary tree.

For $100\%$ of the testdata: $1 \le n \le 2 \times 10^5$, $1 \le a_i \le 5 \times 10^5$.

Special note: This problem uses bundled subtask testing. You will only get the score for a subtask if you pass all test points in that subtask.

Translated by ChatGPT 5