問題文

$N$ 頂点の無向木があります。頂点には $1$ から $N$ までの番号が振られています。辺 $i$ $(1 \leq i \leq N-1)$ は頂点 $u_i$ と頂点 $v_i$ を結びます。

$2$ 頂点 $u,v$ 間の単純パスに含まれる辺の個数を $\text{dist}(u,v)$ と表します。

$k_0=(N!)^2$ とします。

$p=1,2, \ldots ,N$ について、非負整数 $E_p$ を次の式で定義します。

$\begin{aligned} E_p = \sum_{i=1}^{N} \frac{k_0Q_i}{(\text{dist}(p,i)+1)^2} \end{aligned}$

$p=1,2, \ldots ,N$ について、 $E_p$ の値を $998244353$ で割った余りを求めてください。

入力

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

$N$
$Q_1$ $Q_2$ $\ldots$ $Q_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

入力は以下の制約を満たします。

• 入力はすべて整数
• $2 \leq N \leq 200000$
• $1 \leq u_i \lt v_i \leq N$
• $0 \leq Q_i \leq 998244352$

出力

$N$ 行出力してください。 $p$ 行目に $E_p$ の値を $998244353$ で割った余りを出力してください。

最後に改行してください。

サンプル

2
1 2
1 2

6
9

5
8 9 10 11 12
1 2
1 3
1 4
4 5

242400
202800
215600
260800
242300

15
384021089 193015378 976219268 137749749 349176187 734053188 898423703 796747226 1930431 466001235 375378632 199170540 856435845 150579368 391611266
1 11
9 11
7 11
7 12
2 12
3 12
7 13
4 13
10 13
6 13
10 14
5 14
5 15
8 15

164992737
231041473
448643960
643742276
843736071
249725816
936586510
118229251
332387563
883236064
929035671
219161259
34328230
192575536
139074045