Вы проектируете уровень для компьютерной игры. Этот уровень состоит из \(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\) целых чисел — \(k\)-е число должно быть равно минимальному математическому ожиданию дохода игрока, если сундуки расставлены по комнатам в каком-то порядке и ровно \(k\) из сундуков являются мимиками.
Можно показать, что данное математическое ожидание можно представить в виде \(\frac{P}{Q}\), где \(P\) и \(Q\) являются неотрицательными целыми числами \(Q \ne 0\). Выведите значения \(P \cdot Q^{-1} \pmod {998244353}\).
Примечание
В первом примере точные значения минимального математического ожидания равны: \(\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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
499122177 0
|
|
2
|
8
10 4 3 6 5 10 7 5
|
499122193 249561095 249561092 873463811 499122178 124780545 623902721 0
|