Yuta 有一个由 $n$ 个整数组成的序列 $a_1, \dots, a_n$ 和一个数字 $k$。对于该序列的任何非空子序列 $S$，$S$ 的价值定义为 $S$ 中最大的 $\min(|S|, k)$ 个数的和。数组 $a$ 的价值等于其所有非空子序列的价值之和。

现在 Yuta 给出了这 $n$ 个整数，他想知道对于每个 $k \in [1, n]$，数组的价值是多少。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示 Yuta 拥有的序列长度。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示序列本身。

输出格式

输出一行，包含恰好 $n$ 个整数。第 $i$ 个数必须是当 $k = i$ 时数组的价值。由于答案可能非常大，你必须输出它们模 $998244353$ 的结果。

样例

输入样例 1

3
1 1 1

输出样例 1

7 11 12

输入样例 2

5
1 2 3 4 5

输出样例 2

129 201 231 239 240