G. Круговое подземелье
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы проектируете уровень для компьютерной игры. Этот уровень состоит из $$$n$$$ комнат, расположенных по кругу. Комнаты пронумерованы от $$$1$$$ до $$$n$$$. У каждой комнаты ровно один выход: после завершения $$$j$$$-й комнаты вы отправляетесь в $$$(j+1)$$$-ю комнату (а после завершения $$$n$$$-й комнаты вы отправляетесь в $$$1$$$-ю комнату).

Вам задано описание мультимножества из $$$n$$$ сундуков: ценность сокровища в $$$i$$$-м сундуке равна $$$c_i$$$.

Каждый сундук может быть одного из двух типов:

  • обычный сундук — когда игрок заходит в комнату с таким сундуком, то он забирает сокровище и проходит в следующую комнату;
  • сундук-мимик — когда игрок заходит в комнату с таким сундуком, то сундук его съедает, и игрок проигрывает.

Игрок начинает в случайной комнате, и у каждой комнаты равная вероятность быть выбранной. Доход игрока равен сумме ценностей сокровищ в тех сундуках, которые он собрал до своего поражения.

Вы можете выбрать порядок, в котором сундуки будут установлены в комнатах. Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ расставьте сундуки таким образом, что:

  • в каждой комнате находится ровно один сундук;
  • ровно $$$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}$$$.

Примеры
Входные данные
2
1 2
Выходные данные
499122177 0
Входные данные
8
10 4 3 6 5 10 7 5
Выходные данные
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$$$, $$$\frac 3 8$$$, $$$\frac 0 8$$$.