Bạn được cho \(n\) que có độ dài \(a_1,a_2,\dots,a_n\). Bạn phải thực hiện đúng \(k\) nhát cắt lên các que, sao cho số lượng que trở thành \(n + k\).

Sau khi cắt, hiệu giữa độ dài của que dài nhất và que ngắn nhất cần nhỏ nhất có thể. Nhiệm vụ của bạn là tính hiệu nhỏ nhất có thể cho mọi số lượng nhát cắt \(k=1,2,\dots,m\).

Các nhát cắt phải giữ cho độ dài của các que là số nguyên dương. Bạn có thể giả sử rằng các que có thể được cắt \(m\) lần.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n,m\): số lượng que và số nhát cắt tối đa.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\dots,a_n\): độ dài của các que.

Dữ liệu ra

In ra một dòng gồm \(m\) số nguyên: hiệu nhỏ nhất có thể nếu thực hiện đúng \(k=1,2,\dots,m\) nhát cắt.

Constraints

• \(1 \le n \le 10^5\)

• \(1 \le m \le 2 \cdot 10^5\)

• \(1 \le a_i \le 10^9\)

Example

3 3
7 3 2

2 1 2

Explanation

Khi \(k=1\), bạn có thể cắt que thứ nhất thành hai que có độ dài \(3\) và \(4\). Sau đó, độ dài các que là \([3,4,3,2]\) và hiệu lớn nhất là \(2\).