题目背景

LMX 和 HQZ 在研究上次被毙掉的题目 Impacter 时，他们提出了一个新的问题。

题目描述

给定一棵 $n$ 个节点的，以 $1$ 为根的树，每个点有权值 $a_i$。

对于一个点 $u$，定义函数 $f(u,v,d)$ 表示在 $u$ 的子树内选择一些点（至少需要选取一个点），选出的点中最大权值为 $v$，且它们编号的最大公约数为 $d$ 的方案数。

给定一个常数 $k$ 和一个序列 $b$，对于每个点 $u$，你需要求出 $\sum\limits_{k|i}^{n}\sum\limits_{j=1}^nf(u,i,j)\times b_j$ 的值，其中 $k|i$ 表示 $k$ 可以整除 $i$。由于该值可能很大，所以你需要输出其对 $998244353$ 取模的结果。

输入格式

第一行两个整数 $n,k$。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示 $u$ 与 $v$ 之间有一条边。

接下来一行 $n$ 个数，第 $i$ 个数字表示 $a_i$。

接下来一行 $n$ 个数，第 $i$ 个数字表示 $b_i$。

输出格式

一行 $n$ 个整数，分别表示 $u=1,2,\ldots n$ 时的答案对 $998244353$ 取模的值。

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

8 4 2

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

19 5 3 1

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 

475170649 914027313 64013204 696619525 210513956 594697697 111866638 907640826 0 0

提示

样例解释 #1

节点 $3$ 可以选择 $\{3\}$，因为是求最大值为 $1$ 的倍数，所以贡献为 $2$。

节点 $2$ 可以选择 $\{2\},\{3\},\{2,3\}$，因为是求最大值为 $1$ 的倍数，所以贡献是 $1+2+1=4$ 。

节点 $1$ 可以选择 $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$，因为是求最大值为 $1$ 的倍数，所以贡献是 $1+1+2+1+1+1+1=8$ 。

对于所有数据，$1 \le a_i\le n\le 10^5$，$1\le b_i\le 10^9$。

树随机生成*：指对于 $u=2,3,\ldots n$ 每个点，其父亲从 $[1,u-1]$ 的整数中均匀随机选取。