LCA Sum of Products

You are given a tree with (n) nodes numbered from 1 to (n) with node 1 as the root. Each node (i) has two weights: (a_i) and (b_i). The value (a_i) is given, while (b_i) is initially 0.

For every pair of distinct nodes ((u, v)) with (1 \le u < v \le n), let (x = \operatorname{LCA}(u, v)) (the lowest common ancestor of (u) and (v)). If (\gcd(a_u, a_v) > 1) then update (b_x = b_x + a_u \times a_v); otherwise, do nothing.

Your task is to compute (b_i \bmod 998244353) for each node (i) ((1 \le i \le n)).

Note: If one node is an ancestor of the other, then the ancestor is their LCA.

inputFormat

The first line contains an integer (n) representing the number of nodes in the tree.

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

Each of the next (n-1) lines contains two space-separated integers (u) and (v) representing an edge between nodes (u) and (v). It is guaranteed that the given graph is a tree with node 1 as the root.

outputFormat

Output a single line containing (n) space-separated integers where the (i)th integer is (b_i \bmod 998244353).

sample

3
2 3 4
1 2
1 3

8 0 0