Annettuna on $n$ tikkua, joilla on pituudet $a_1,a_2,\dots,a_n$. Sinun tulee tehdä tikkuihin täsmälleen $k$ leikkausta siten, että tikkujen määräksi tulee $n + k$.

Leikkausten jälkeen pisimmän ja lyhimmän tikun pituuden erotus halutaan mahdollisimman pieneksi. Tehtäväsi on laskea pienin mahdollinen erotus kaikille määrille $k=1,2,\dots,m$.

Leikkausten on säilytettävä tikkujen pituudet positiivisina kokonaislukuina. Voit olettaa, että tikkuihin on mahdollista tehdä $m$ leikkausta.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n,m$: tikkujen määrä ja leikkausten enimmäismäärä.

Toisella rivillä on $n$ kokonaislukua $a_1,a_2,\dots,a_n$: tikkujen pituudet.

Tuloste

Tulosta yhdelle riville $m$ lukua: mikä on pienin mahdollinen erotus pisimmän ja lyhimmän tikun pituuden välillä, jos tehdään täsmälleen $k=1,2,\dots,m$ leikkausta.

Esimerkki

Syöte:

3 3
7 3 2

Tuloste:

2 1 2

Osatehtävä 1 (7 pistettä)

• $1 \le n \le 5$
• $1 \le m \le 10$
• $1 \le a_i \le 10$

Osatehtävä 2 (8 pistettä)

• $1 \le n \le 1000$
• $1 \le m \le 2000$
• $1 \le a_i \le 3$

Osatehtävä 3 (12 pistettä)

• $1 \le n \le 1000$
• $1 \le m \le 2$
• $1 \le a_i \le 1000$

Osatehtävä 4 (24 pistettä)

• $1 \le n \le 100$
• $1 \le m \le 200$
• $1 \le a_i \le 200$

Osatehtävä 5 (31 pistettä)

• $1 \le n \le 1000$
• $1 \le m \le 2000$
• $1 \le a_i \le 10^9$

Osatehtävä 6 (18 pistettä)

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