Hồng đã soạn được \(n\) bài tập Tin học, bài thứ ݅\(i(1 \le i \le ݊n)\) có độ khó là số nguyên dương \(c_i\). Hồng được cô giáo yêu cầu gửi \(m\) bài tập lên hệ thống luyện tập trực tuyến để tập huấn cho một nhóm các em học sinh khóa dưới. Nếu \(m < n\), khi đó, Hồng phải loại bỏ \(n - m\) bài tập, ngược lại nếu \(m > n\) thì Hồng phải soạn thêm \(m - n\) bài tập với độ khó là số nguyên dương. Khi đưa lên hệ thống \(m\) bài tập, Hồng sẽ sắp xếp các bài theo độ khó tăng dần, gọi \(d\) là chênh lệch độ khó lớn nhất của hai bài tập liên tiếp. Hồng mong muốn giá trị \(d\) nhỏ nhất có thể.

Yêu cầu: Cho \(n\) bài tập với độ khó là ܿ\(c_1, c_2, ..., c_n\) và số \(m\), hãy tìm giá trị \(d\) nhỏ nhất.

Input

Vào từ thiết bị vào chuẩn:

• Dòng đầu gồm hai số nguyên dương ݊\(n, m (2 \le m, n \le 10^5; m \ne n)\);
• Dòng thứ hai gồm ݊ số nguyên dương \(c_1, c_2, ..., c_n\) \((c_i \le 10^9, 1 \le i \le n)\).

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên \(d\) tìm được.

Example

5 4
8 5 9 10 10

1

3 4
8 6 9

1