在最近的一次星际拾荒之旅中，你发现了一个被遗弃的未来机器人。神秘的是，这个机器人由 $n$ 个球形关节组成，内部含有某种液体。这些关节通过 $n-1$ 根柔性管道连接在一起，允许液体在关节之间双向流动。为了分析机器人内部这种奇怪的液体，你决定使用离心机。

由于你根本不知道如何使用离心机，你将其中一个关节固定在离心机的中心，然后启动机器。机器绕着中心高速旋转，所有的液体都被从中心向外推。每当液体有超过一条管道可以流过时，液体就会在这些管道之间均匀分配。

你很好奇在这个过程结束时，最外层的关节中会有多少液体。在思考了很久之后，你忘记了你将哪个关节固定在了中心。因此，你需要计算如果随机选择一个关节作为中心，每个关节中液体的期望量。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示机器人的关节数量。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^9$)，表示第 $i$ 个关节中的液体量。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示关节 $u$ 和 $v$ 之间有一根管道。这些管道构成了一棵树。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行表示在过程结束后，第 $i$ 个关节中液体量的期望值，对 $998\,244\,353$ 取模。

形式上，令 $M = 998\,244\,353$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod M$。输出等于 $p \cdot q^{-1} \pmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$。

样例

样例输入 1

3
1 2 4
1 2
2 3

样例输出 1

3
0
4

样例输入 2

6
4 1 3 11 7 2
1 4
2 3
6 2
2 4
4 5

样例输出 2

928921837
0
818005794
0
679360751
568444705

说明

在第一个样例中，如果第一个关节被固定在中心，所有的液体将从关节 1 流向 2，合并后的液体将流向 3。总的来说，关节 1 和 2 将为空，所有 7 个单位的液体都将在关节 3。

如果第二个关节被固定在中心，它的一半液体将流向 1，另一半流向 3。此时各关节的液体量分别为 2、0 和 5。如果关节 3 被固定，所有 7 个单位的液体都将在关节 1。

总的来说，每个关节中液体量的期望值为： $$\frac{1}{3} \cdot (0 + 2 + 7) = 3$$ $$\frac{1}{3} \cdot (0 + 0 + 0) = 0$$ $$\frac{1}{3} \cdot (7 + 5 + 0) = 4$$