链接: https://cses.fi/problemset/task/3401

板块: Additional Problems II

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定 $n$ 根长度分别为 $a_1,a_2,\dots,a_n$ 的木棍。你必须对木棍恰好切 $k$ 刀，使木棍数量变为 $n+k$。

切完后，最长与最短木棍的长度差应尽可能小。你的任务是对所有 $k=1,2,\dots,m$ 计算这个最小可能差值。

切法必须保持木棍长度为正整数。可假设木棍可被切 $m$ 次。

输入

第一行包含两个整数 $n,m$：木棍数与最大切割数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$：木棍的长度。

输出

输出一行 $m$ 个整数：恰好切 $k=1,2,\dots,m$ 刀时的最小可能差值。

数据范围

$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