题目描述

现在有 $n$ 个糖果，每个糖果有一种颜色 $c_i$。

现在高桥君想要在中间选 $k$ 个糖果。由于他想吃最多种颜色的糖果，所以他的快乐值是选择的糖果的颜色种类数。

例如，选择糖果的颜色是 $\{2,3,3\}$，那么他的快乐值是 $2$。

对于 $\forall k \in [1,n]$，求出高桥君随机选择 $k$ 个糖果的快乐值的期望值，对 $998244353$ 取模。

$n \le 5 \times 10^4$，$c_i \le 10^9$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $c_i$。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行表示 $k = i$ 时的答案，对 $998244353$ 取模。

3
1 2 2

1
665496237
2

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

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7