您正在为视频游戏创建关卡。该级别由放置在一个圆圈中的 $$$n$$$ 个房间组成。房间编号为 $$$1$$$ 到 $$$n$$$。每个房间都包含一个出口:完成第 $$$j$$$ 个房间可以让您前往第 $$$(j+1)$$$ 个房间(完成第 $$$n$$$ 个房间可以让您前往第 $$$1$$$ 个房间)。
向您提供了 $$$n$$$ 个箱子的多组描述:第 $$$i$$$ 个箱子具有宝藏价值 $$$c_i$$$。
每个箱子可以是以下两种类型之一:
- 普通宝箱——当玩家进入带有此宝箱的房间时,他会抓住宝藏并前往下一个房间;
- 模拟宝箱 - 当玩家进入带有该宝箱的房间时,宝箱会把他活活吃掉,他就输了。
玩家从一个随机房间开始,每个房间被选择的概率相同。玩家的收入等于他输掉之前收集的宝箱的总价值。
你可以选择箱子进入房间的顺序。对于从$$$1$$$到$$$n$$$的每个$$$k$$$,将箱子放入房间中的方式如下:
- 每个房间恰好包含一个箱子;
- $$$k$$$ 箱子是模仿品;
- 玩家收入的预期值是最低的。
请注意,对于每个 $$$k$$$,放置位置都是独立选择的。
可以证明它的形式为$$$\frac{P}{Q}$$$,其中$$$P$$$和$$$Q$$$是非负整数,$$$Q \ne 0$$$。报告 $$$P \cdot Q^{-1} \pmod {998244353}$$$ 的值。
输入
第一个包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 房间数量和箱子数量。
第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$) — 每个箱子的宝藏值。
输出
打印 $$$n$$$ 整数 - 如果箱子按某种顺序放置在房间中,并且箱子中的 $$$k$$$ 是模仿品,则第 $$$k$$$ 值应等于玩家收入的最小可能预期值。
可以证明它的形式为$$$\frac{P}{Q}$$$,其中$$$P$$$和$$$Q$$$是非负整数,$$$Q \ne 0$$$。报告 $$$P \cdot Q^{-1} \pmod {998244353}$$$ 的值。
示例
输入 #1
2 1 2
输出 #1
499122177 0
输入 #2
8 10 4 3 6 5 10 7 5
输出 #2
499122193 249561095 249561092 873463811 499122178 124780545 623902721 0
注意
在第一个示例中,最小期望值的确切值为:$$$\frac 1 2$$$、$$$\frac 0 2$$$。
在第二个示例中,最小期望值的确切值为: $$$\frac{132} 8$$$、$$$\frac{54} 8$$$、$$$\frac{30} 8$$$、$$$\frac{17} 8$$$、$$$\frac{12} 8$$$、$$$\frac 7 8$$$、 $$$\压裂3 8$$$,$$$\压裂0 8$$$。