Problem

頂点 $0$ を根とする $N$ 頂点の根付き木と、長さ $N$ の数列 $A$ が与えられます。
与えられる根付き木の $i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいます。
$C(i)$ を、頂点 $i$ の子であるような頂点の番号の集合とします。
長さ $N$ の数列 $B_i$ を以下のように定義します。

• $i=0$ なら $(B_i)_j=A_j$
• $i>0$ なら $\displaystyle (B_i)_j=(B_{i-1})_j + \sum_{k \in C(j)} (B_i)_k$

数列 $B_M$ を求めてください。
ただし、$B_M$ の各項は非常に大きくなることがあるので、$998244353$ で割ったあまりを出力してください。

Input

入力は以下の形式で与えられる。

$N$ $M$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$u_0$ $v_0$
$\vdots$
$u_{N-2}$ $v_{N-2}$

Constraints

入力は以下の条件を満たす。

• $2 \leq N \leq 2\times 10^5$
• $1 \leq M \lt 998244353$
• $0 \leq A_i \lt 998244353$
• $0 \leq u_i,v_i \leq N-1$
• 与えられるグラフは木である
• 入力は全て整数である

Output

$(B_M)_0,(B_M)_1,\ldots ,(B_M)_{N-1}$ を $998244353$ で割ったあまりをこの順に空白で区切って一行に出力する。

Sample Input 1

2 100000000
1 1
0 1

Sample Output 1

100000001 1

Sample Input 2

5 1
1 10 100 1000 10000
0 1
1 2
1 3
0 4

Sample Output 2

11111 1110 100 1000 10000

Sample Input 3

5 998244352
1 10 100 1000 10000
0 1
1 2
1 3
0 4

Sample Output 3

998234344 998243263 100 1000 10000

---