样例下载

题目描述

$N$ 头奶牛，编号为 $1$ ~ $N$。

奶牛 $i$ 的身高为 $H_i$（注：$H_i$ 为非负整数，可能存在身高为 $0$ 的奶牛）。

定义奶牛 $i$ 的 RANK 为所有身高不低于 $H_i$ 的奶牛数目（包含奶牛 $i$ 自己），即： $\sum\limits_{j=1}^N （H_j ≥ H_i ? 1 :0 ）$

例如：$4$ 头奶牛的身高分别为 $1, 2, 3, 3$，则它们的 RANK 分别为 $4, 3, 2, 2$.

某天，有 $M$ 头奶牛误食了毒苹果，导致身高变成了原来的两倍。但并不知道是哪 $M$ 头奶牛。所以误食情况有 $C(N, M)$ 种。

问：对于奶牛 $i$，有多少种可能的误食情况，它的 RANK 并没有发生变化？答案可能很大，你只需要输出答案 $mod$ $998244353$ 的值。

输入

第一行：包含两个正整数 $N, M$

第二行：包含 $N$ 个整数 $H_i$

输出

共 $N$ 行，每行一个整数，第 $i$ 行的整数表示奶牛 $i$ 的答案 $mod$ $998244353$。

样例输入

3 2
0 1 2

样例输入

3
3
2

样例解释

样例中，奶牛 1, 2, 3 的身高分别为 0, 1, 2, RANK 分别为 3, 2, 1。

共有 C(3, 2) = 3 种可能的误食情况：

（1）奶牛 1 和奶牛 2 误食；此时身高分别为 0, 2, 2, RANK 分别为 3, 2, 2。

（2）奶牛 1 和奶牛 3 误食；此时身高分别为 0, 1, 4, RANK 分别为 3, 2, 1。

（3）奶牛 2 和奶牛 3 误食；此时身高分别为 0, 2, 4, RANK 分别为 3, 2, 1。

对于奶牛 1 和 奶牛 2，以上 3 种可能情况下，它们的 RANK 均没有发生变化。

对于奶牛 3，在第 （1） 种情况下，它的 RANK 变成了 2，在另两种情况下没有变化。

数据范围

10% 的数据，有 $1 ≤ N ≤ 20$

35% 的数据，有 $1 ≤ N ≤ 10^3$

另有 10% 的数据，$H_i$ 两两不同

另有 10% 的数据， $0 ≤ H_i ≤ 10^5$

另有 10% 的数据，满足 $0 ≤ H_i ≤ 10^3$

100% 的数据，有 $1 ≤ M < N ≤ 10^5, 0 ≤ H_i ≤ 10^9$