시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

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 defined as the sum of the largest $\min(|S|, k)$ numbers in $S$. The value of the array $a$ is equal to the sum of the values of all its non-empty subsequences.

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

입력

The first line of the input 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.

출력

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

예제 입력 1

3
1 1 1

예제 출력 1

7 11 12

예제 입력 2

5
1 2 3 4 5

예제 출력 2

129 201 231 239 240