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