题目描述

给定 $n$ 根木棍，长度为 $a_1,a_2,\ldots,a_n$。你必须恰好切割 $k$ 次，使木棍数量变为 $n+k$。

切割后，最长木棍与最短木棍的长度差应尽量小。请对每个 $k=1,2,\ldots,m$，计算该最小可能差值。

每次切割后木棍长度必须仍为正整数。保证木棍总共可以被切割 $m$ 次。

输入格式

第一行包含两个整数 $n,m$，分别表示木棍数量和最大切割次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示木棍长度。

输出格式

输出一行 $m$ 个整数，第 $k$ 个表示恰好切割 $k$ 次时的最小可能差值。

数据范围

• $1 \le n \le 10^5$
• $1 \le m \le 2\cdot 10^5$
• $1 \le a_i \le 10^9$

样例

样例输入

3 3
7 3 2

样例输出

2 1 2

样例说明

当 $k=1$ 时，可以将长度为 $7$ 的木棍切成 $3$ 和 $4$，此时所有木棍长度为 $[3,4,3,2]$，最大差值为 $2$。