Value of the Array

Time limit1sMemory limit512 MB

Summary

For each k from 1 to n, sum over all non-empty subsequences the sum of their min(size, k) largest elements, modulo 998244353.

Level: Hard8 of 10
Topics: Combinatorics, Sorting, Math, Prefix sum
Solved: No attempts yet

Problem

Yuta has a sequence of $n$ integers $a_1, \ldots, a_n$ and a number $k$ . For any non-empty subsequence $S$ of this sequence, the value of $S$ is the sum of the largest $\min(|S|, k)$ numbers in $S$ . The value of the array $a$ is the sum of the values of all its non-empty subsequences.

Yuta shows the $n$ integers and wants to know the value of the array for each $k \in [1, n]$ .

Input

The first line contains an integer $n$ ( $1 \le n \le 10^5$ ), the length of the sequence Yuta has. The second line contains $n$ integers $a_1, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ), the sequence itself.

Output

Print one line with exactly $n$ integers. The $i$ -th number must be the value of the array when $k = i$ . The answers may be very large, so print them modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
3
1 1 1
```
Expected output
```
7 11 12
```
Example 2
Input
```
5
1 2 3 4 5
```
Expected output
```
129 201 231 239 240
```