和的期望
题号：NC264714
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一个长度为 n 的数组 a，和一个空数组 b。

现在将进行 k 次操作，每次操作将从数组 a 等概率选择一个数，将其从数组 a 中删除，并加入到 b 数组。

请对于每一个 k = 1, 2, \ldots, n，求出数组 b 的和的期望。

输入描述:

第一行一个整数 n(1 \leqslant n \leqslant {10}^5) 表示数组长度。

接下来一行 n 个整数，第 i 个整数表示 a_i (1 \leqslant a_i \leqslant {10}^9) 的值。

输出描述:

输出一行 n 个整数，第 i 个整数表示 k = i 时，数组 b 的和的期望对 998244353 取模。

可以证明，最终的答案一定可以表示成最简分数 \displaystyle\frac{P}{Q}，其中 P, Q 是正整数且 Q \not\equiv 0 \pmod {998244353}。你需要输出一个整数 0 \leqslant x < 998244353 使得 x \cdot Q \equiv P \pmod {998244353}，可以证明这样的 x 是唯一的。
示例1

输入

复制 
2
1 2

输出

复制 
499122178 3

说明

当 k = 1 时：
\bullet 有 \frac{1}{2} 的概率将 1 加入到数组 b 得到 a = [2], b = [1]；
\bullet 有 \frac{1}{2} 的概率将 2 加入到数组 b 得到 a = [1], b = [2]；
\bullet 故数组 b 的和的期望为 \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = \frac{3}{2}。
\bullet 499122178 \cdot 2 \equiv 3 \pmod {998244353}，故输出 499122178。

当 k = 2 时：
\bullet 有 \frac{1}{2} 的概率依次将 1, 2 加入到数组 b 得到 a = [], b = [1, 2]；
\bullet 有 \frac{1}{2} 的概率依次将 2, 1 加入到数组 b 得到 a = [], b = [2, 1]；
\bullet 故数组 b 的和的期望为 \frac{1}{2} \cdot (1 + 2) + \frac{1}{2} \cdot (2 + 1) = 3。
示例2

输入

复制 
3
2333 114514 1919810

输出

复制 
666175121 334105889 2036657