4073. 棋局

【题目背景】

$NOIP$ $2024$烽烟似起......

【题目描述】

有个 $n$ 行 $m$ 列的棋盘，每个格子上有 $0$ 或 $1$ 个棋子。小小忘记棋局的模样，只记得第 $i$ 行有不少于 $a_i$ 个棋子。

对于每个 $1≤k≤n$，请你帮助小小计算：在所有可能的棋局中，棋子数不少于 $k$ 个的列数最少是多少。

【输入格式】

第一行包含两个数 $n$ 和 $m$。

第二行包含 $n$ 个数：$a_1，a_2，......，a_n$，含义见题目描述。

【输出格式】

输出一行，包含 $n$ 个数，第 $i$ 个为 $k=i$ 的答案。

【样例输入1】

3 4
1 2 3

【样例输出1】

310

【样例输入2】

4 5
5 3 4 4

【样例输出2】

5 4 3 1

【样例输入3】

5 5
2 3 4 4 4

【样例输出3】

4 4 3 1 0

【样例输入4】

30 30
24 10 0 12 14 27 5 17 12 14 20 2 22 15 28 18 26 16 19 12 21 24 9 1 19 25 24 26 0 24

【样例输出4】

28 26 24 23 22 21 19 18 16 14 13 11 10 8 6 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0

【样例5】

点击下载样例5 

【数据规模与约定】

对于 $20\%$ 的数据，$n，m≤5$。

对于 $40\%$ 的数据，$n，m≤30$。

对于 $60\%$ 的数据，$n，m≤2500$。

对于 另外 $20\%$ 的数据，$a_i=m-1$。

对于 $100\%$ 的数据，$1≤n≤2×10^5，1≤m≤10^8，0≤a_i≤m$。