在战前，蛐蛐国土地肥沃，农业发达，素有“沃野千里，天府之土”的美誉。农业是蛐蛐国的一大支柱产业。但在连年战乱后，蛐蛐国遭遇了严重水土流失，土质受到严重破坏，粮食和经济作物产量大大降低。振兴蛐蛐国农业，成为蛐蛐国的一大要务和难题。

伏特决定用跳蚤国的高新技术——金坷垃来解决这个难题。金坷垃是一种知名肥料，一袋能顶两袋撒，撒了小麦亩产一千八。即使面对蛐蛐国的恶劣土壤环境，金坷垃也可以极大提升作物产量。

但是金坷垃并不能单独使用，只能加入到一款其它的肥料中混合使用。同时金坷垃的作用有着极强的随机性：若一款原有的肥料肥力被量化为整数 $x$ ，则将金坷垃掺入其中后，会带来一定的额外肥力，数值在 $[0,m]$ 间等概率随机，即，新的肥料肥力会变为 $[x,x+m]$ 之间的等概率随机实数，这里 $m$ 是一个给定的整数。

现在伏特想测试下金坷垃的性能，他从市面上买了 $n$ 款肥料，并将金坷垃分别掺入其中，不同肥料间掺入金坷垃后金坷垃带来的额外肥力互不相关。他希望你能告诉他，最终得到的肥料肥力中排序后第 $1\sim n$ 小的肥力期望值分别是多少。可以证明在题目的条件限制下，期望值是一个最简分数 $\frac{p}{q}$ ，且 $q$ 不是 $998244353$ 的倍数，你只需要输出 $p\cdot q^{-1}mod998244353$ 的值即可。

输入格式

第一行两个正整数 $n,m$ ，分别表示肥料种类数和金坷垃的肥力上限。

接下来一行 $n$ 个正整数，第 $i$ 个正整数 $a_i$ 表示第 $i$ 款肥料的肥力。

输出格式

输出 $n$ 行，第 $i$ 行一个非负整数表示第 $i$ 小的肥力期望值对 $998244353$ 取模后的值。

样例一

input

3 1
1 2 3

output

499122178
499122179
499122180

explanation

三款肥料的肥力分别是 $a_1=1,a_2=2,a_3=3$ ，且 $m=1$ 。

容易发现不论金坷垃带来的额外肥力是多少，最终得到的三款肥料肥力 $b_i$ 仍然满足 $b_1\le b_2\le b_3$ 。因此第 $i$ 小肥料肥力期望值即为 $b_i$ 期望值 $\frac{3}{2},\frac{5}{2},\frac{7}{2}$ ，对 $998244353$ 取模后即得到样例输出。

样例二

input

5 3
3 4 2 3 5 

output

505489582
791406484
246480092
249971894
702262855

样例三

见附加文件中 ex_fertilizer3.in 和 ex_fertilizer3.out 。

样例四

见附加文件中 ex_fertilizer4.in 和 ex_fertilizer4.out 。

数据范围

对于所有数据， $1\le n\le 2000,1\le m,a_i\le {10}^8$ 。

时间限制：$4\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载