Tree Subset GCD and Maximum Weight

Given a rooted tree with n nodes (numbered from 1 to n) and root 1. Each node i has an integer weight \(a_i\). Consider a node \(u\) and its subtree. For any nonempty subset \(S\) of nodes in the subtree of \(u\), define:

• \(v = \max_{x \in S} a_x\), the maximum weight among the chosen nodes.
• \(d = \gcd(S)\), the greatest common divisor of the indices of the chosen nodes (i.e. \(\gcd(\{x:\; x\in S\})\)).

Let \(f(u,v,d)\) be the number of ways to choose a nonempty subset \(S\) from the subtree of \(u\) such that the maximum weight is \(v\) and \(\gcd(S)=d\). You are also given a constant integer \(k\) and a sequence \(b_1, b_2, \dots, b_n\). For each node \(u\), compute

[ \sum_{\substack{1 \le v \le n \ k\mid v}} ;\sum_{d=1}^{n} f(u,v,d) \times b_d \mod 998244353, ]

where \(k\mid v\) denotes that \(k\) divides \(v\). Equivalently, for each node \(u\), for every nonempty subset \(S\) of its subtree, if \(v = \max_{x \in S}a_x\) is divisible by \(k\) then add \(b_{\gcd(\{x\in S\})}\) to the answer.

inputFormat

The input is given as follows:

 n k
 a[1] a[2] ... a[n]
 u1 v1
 u2 v2
 ...
 u{n-1} v{n-1}
 b[1] b[2] ... b[n]

Here:

• \(n\) is the number of nodes.
• \(k\) is the given constant.
• The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), the weights of the nodes.
• Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) denoting an undirected edge. The tree is rooted at node 1.
• The last line contains \(n\) integers \(b_1, b_2, \dots, b_n\).

You may assume that \(n\) is small enough (for example, \(n \le 15\)) so that a brute force solution over all subsets in each subtree is feasible.

outputFormat

Output \(n\) lines. The \(i\)th line should contain the answer for node \(i\) (i.e. the computed value modulo \(998244353\)).

sample

3 2
2 3 4
1 2
1 3
1 2 3

7
0
3