Problem Description

Given a tree with \( n \) nodes rooted at node \( 1 \), each node has two values \( a_i \) and \( b_i \) (\( 1 \le i \le n \)). The values \( a_i \) are provided, and \( b_i \) are initially set to \( 0 \).

For each 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 \( b_x \gets b_x + a_u \times a_v \); otherwise, no operation is performed.

For each \( 1 \le i \le n \), compute \( b_i \mod 998244353 \).

Input Format

The first line contains an integer \( n \), representing the number of nodes.

The second line contains \( n \) positive integers, representing \( a_1, a_2, \ldots, a_n \).

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

Output Format

Output consists of \( n \) lines, each containing an integer.

The \( i \)-th line represents \( b_i \mod 998244353 \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

785
0
0
1972
144
0
0
0

Input Sample #2

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

Output Sample #2

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

Notes

Sample Explanation

The constructed tree is shown in the image.

The contributions are as follows:

• For node \( 1 \):

• Pair \( (3, 4) \) contributes \( 4 \).

• Pair \( (3, 5) \) contributes \( 4 \).
• Pair \( (3, 7) \) contributes \( 144 \).
• Pair \( (3, 8) \) contributes \( 48 \).
• Pair \( (1, 6) \) contributes \( 9 \).
• Pair \( (1, 7) \) contributes \( 216 \).
• Pair \( (1, 8) \) contributes \( 72 \).
• Pair \( (6, 7) \) contributes \( 216 \).
• Pair \( (6, 8) \) contributes \( 72 \).

Total: \( 785 \).

• For node \( 4 \):

• Pair \( (4, 5) \) contributes \( 4 \).

• Pair \( (4, 7) \) contributes \( 144 \).
• Pair \( (4, 8) \) contributes \( 48 \).
• Pair \( (5, 8) \) contributes \( 48 \).
• Pair \( (7, 8) \) contributes \( 1728 \).

Total: \( 1972 \).

• For node \( 5 \):

• Pair \( (5, 7) \) contributes \( 144 \).

Total: \( 144 \).

Other nodes clearly contribute \( 0 \).

Data Range

Special Property A: All \( a_i \) are randomly generated.

Special Property B: The tree is a complete binary tree.

For \( 100\% \) of the data, \( 1 \le n \le 2 \times 10^5 \), \( 1 \le a_i \le 5 \times 10^5 \).

Special Note: This problem uses subtask-based scoring. You must pass all test cases in a subtask to earn the points for that subtask.

见题面 Input 部分

见题面 Output 部分