问题描述

有 $N$ 张卡片，分别称为卡片 $1$、卡片 $2$、$\\ldots$、卡片 $N$。在卡片 $i$ 上 $(1\\leq i\\leq N)$，写有一个整数 $A_i$。

对于 $K=1, 2, \\ldots, N$，解决以下问题。

我们有一个袋子，里面装有 $K$ 张卡片：卡片 $1$、卡片 $2$、$\\ldots$、卡片 $K$。
让我们进行以下操作两次，并且按照记录的顺序记下数值 $x$ 和 $y$。

从袋子中等概率地随机抽取一张卡片，并记录卡片上的数字。然后，将该卡片放回袋子。

求 $\\max(x,y)$ 的期望值，对 $998244353$ 取模（见注释）。
这里，$\\max(x,y)$ 表示 $x$ 和 $y$ 中较大的那个数的值（如果它们相等，则取 $x$）。

注释

可以证明所求的期望值始终是有限且有理数。此外，在本问题的约束条件下，当该值表示为具有互质整数 $P$ 和 $Q$ 的 $\\frac{P}{Q}$ 形式时，可以证明存在唯一的整数 $R$，满足 $R \\times Q \\equiv P\\pmod{998244353}$ 且 $0 \\leq R \\lt 998244353$。请输出 $R$。

约束条件

• $1 \\leq N \\leq 2\\times 10^5$
• $1 \\leq A_i \\leq 2\\times 10^5$
• 输入中的所有值均为整数。

输入

从标准输入读取输入数据，输入格式如下：

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$

输出

输出 $N$ 行。第 $i$ 行 $(1\\leq i\\leq N)$ 应包含问题 $K=i$ 的答案。

样例输入 1

3
5 7 5

样例输出 1

5
499122183
443664163

例如，对于 $K=2$ 的答案如下。

袋子中有卡片 $1$ 和卡片 $2$，它们上面分别写着 $A_1=5$ 和 $A_2=7$。

• 如果你在第一次抽卡时抽到了卡片 $1$，并在第二次抽卡时再次抽到了卡片 $1$，那么我们有 $x=y=5$，所以 $\\max(x,y)=5$。
• 如果你在第一次抽卡时抽到了卡片 $1$，并在第二次抽卡时抽到了卡片 $2$，那么我们有 $x=5$ 和 $y=7$，所以 $\\max(x,y)=7$。
• 如果你在第一次抽卡时抽到了卡片 $2$，并在第二次抽卡时抽到了卡片 $1$，那么我们有 $x=7$ 和 $y=5$，所以 $\\max(x,y)=7$。
• 如果你在第一次抽卡时抽到了卡片 $2$，并在第二次抽卡时再次抽到了卡片 $2$，那么我们有 $x=y=7$，所以 $\\max(x,y)=7$。

这些事件发生的概率相同，因此所求的期望值为 $\\frac{5+7+7+7}{4}=\\frac{13}{2}$。我们有 $499122183\\times 2\\equiv 13 \\pmod{998244353}$，所以应该输出 $499122183$。

样例输入 2

7
22 75 26 45 72 81 47

样例输出 2

22
249561150
110916092
873463862
279508479
360477194
529680742