Linh kiện

Hồng là một giáo viên Tin học năng động, được giao nhiệm vụ chuẩn bị các bài tập luyện tập cho một nhóm học sinh khóa dưới. Hồng đã soạn được \(n\) bài tập, bài tập thứ \(i\) có độ khó là số nguyên dương \(c_i\).

Tuy nhiên, cô giáo yêu cầu Hồng chỉ gửi \(m\) bài tập lên hệ thống trực tuyến. Do đó:

• Nếu \(m < n\), Hồng phải loại bỏ \(n - m\) bài tập.
• Nếu \(m > n\), Hồng phải soạn thêm \(m - n\) bài tập mới với độ khó là các số nguyên dương.

Sau khi có đủ \(m\) bài tập, Hồng sẽ sắp xếp chúng theo độ khó tăng dần. Gọi \(d\) là chênh lệch độ khó lớn nhất giữa hai bài tập liên tiếp trong danh sách bài tập đã sắp xếp. Hồng mong muốn giá trị \(d\) là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) \((2 \leq m, n \leq 10^5; m \neq n)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(c_1, c_2, \dots, c_n\) \((1 \leq c_i \leq 10^9)\).

Output

• Ghi ra một số nguyên \(d\) là giá trị chênh lệch độ khó lớn nhất nhỏ nhất có thể đạt được.

Example

5 4
8 5 9 10 10

1

3 4
8 6 9

1