问题陈述

有$N$个糖果从左到右排列。
每个糖果有以下$10^9$种颜色之一：颜色$1$，颜色$2$，$\ldots$，颜色$10^9$。
对于每个$i = 1, 2, \ldots, N$，从左边数第$i$个糖果的颜色为$c_i$。

高桥将从这$N$个糖果中选择$K$个并拿走这些$K$个糖果。
从这$N$个糖果中选择$K$个的方法有$\binom{N}{K}$种，其中$\binom{N}{K}$是二项系数。高桥将以等概率随机选择这$\binom{N}{K}$种方式中的一种。

因为高桥想吃多彩的糖果，他的糖果颜色种类越多，他就越开心。
对于每个情景$K = 1, 2, \ldots, N$，计算高桥的糖果所拥有不同颜色的期望值。
我们可以证明所求值是一个有理数。按照说明，将这个有理数对$998244353$取模，并打印出结果。

说明

当打印一个有理数时，首先将其表示为分数$\frac{y}{x}$，其中$x, y$为整数且$x$不可被$998244353$整除（在问题的约束下，总能找到这样一个表示）。然后，你需要打印唯一的整数$z$，它满足$xz \equiv y \pmod{998244353}$，其中$0 \leq z \leq P - 1$。

约束条件

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq c_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $c_1$ $c_2$ $\ldots$ $c_N$

输出

打印$N$行。第$i$行应包含高桥的糖果在情景$K = i$下拥有不同颜色的期望值，结果对$998244353$取模。

示例输入1

3
1 2 2

示例输出1

1
665496237
2

当$K = 1$时，他会得到第$1$个糖果、第$2$个糖果或第$3$个糖果。无论如何，他的糖果只有一种颜色，所以不同颜色的期望值是$1$。

当$K = 2$时，他会得到第$1$个和第$2$个糖果、第$2$个和第$3$个糖果，或者第$1$个和第$3$个糖果。

• 如果他得到第$1$个和第$2$个糖果，它们有两种不同的颜色。
• 如果他得到第$2$个和第$3$个糖果，它们只有一种颜色。
• 如果他得到第$1$个和第$3$个糖果，它们有两种不同的颜色。

因此，不同颜色的期望值是$\frac{1}{3} \cdot 2 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{5}{3}$。
请确保按照说明，将结果对$998244353$取模后打印。

当$K = 3$时，他总是会得到第$1$个、第$2$个和第$3$个糖果，它们有两种不同的颜色，所以不同颜色的期望值是$2$。

示例输入2

11
3 1 4 1 5 9 2 6 5 3 5

示例输出2

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7