Problem Background

LMX and HQZ, while studying the previously rejected problem Impacter, came up with a new problem.

Problem Description

Given a tree with $n$ nodes rooted at $1$, each node has a value $a_i$.

For a node $u$, define the function $f(u,v,d)$ as the number of ways to select some nodes (at least one) within the subtree of $u$, where the maximum value among the selected nodes is $v$, and the greatest common divisor of their indices is $d$.

Given a constant $k$ and a sequence $b$, for each node $u$, you need to compute the value of $\sum\limits_{k|i}^{n}\sum\limits_{j=1}^n f(u,i,j) \times b_j$, where $k|i$ denotes that $k$ divides $i$. Since this value can be very large, you need to output the result modulo $998244353$.

Input Format

The first line contains two integers $n$ and $k$.

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

The next line contains $n$ numbers, the $i$-th number being $a_i$.

The next line contains $n$ numbers, the $i$-th number being $b_i$.

Output Format

A single line containing $n$ integers, representing the answers for $u=1, 2, \ldots, n$ modulo $998244353$.

Sample Input and Output

Sample Input #1

3 1
1 2
2 3
1 1 2
1 1 2

Sample Output #1

8 4 2

Sample Input #2

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

Sample Output #2

19 5 3 1

Sample Input #3

10 3
1 2
1 3
2 4
2 5
3 6
3 7
7 8
5 9
9 10
1 3 7 3 6 6 6 9 4 8 
450163553 649444963 324825063 696619525 758594756 594697697 750550965 907640826 118301481 755848673 

Sample Output #3

475170649 914027313 64013204 696619525 210513956 594697697 111866638 907640826 0 0

Notes

Sample Explanation #1

For node $3$, the possible selection is $\{3\}$, and since we are looking for multiples of $1$, the contribution is $2$.

For node $2$, the possible selections are $\{2\}$, $\{3\}$, and $\{2,3\}$, and since we are looking for multiples of $1$, the contribution is $1 + 2 + 1 = 4$.

For node $1$, the possible selections are $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, and $\{1,2,3\}$, and since we are looking for multiples of $1$, the contribution is $1 + 1 + 2 + 1 + 1 + 1 + 1 = 8$.

For all data, $1 \le a_i \le n \le 10^5$, $1 \le b_i \le 10^9$.

Tree generated randomly*: For each node $u = 2, 3, \ldots, n$, its parent is chosen uniformly at random from $[1, u-1]$.

见题面 Input 部分

见题面 Output 部分