농장의 공통 안내선

문제

한 농장은 여러 재배 줄에 놓인 센서의 위치를 한 장의 작업 도면으로 관리한다. 각 재배 줄에는 센서가 하나씩 있으며, 센서의 위치는 모든 줄에서 같은 기준점을 사용하는 정수 좌표로 기록되어 있다. 서로 다른 줄의 센서는 같은 좌표에 있을 수도 있다. 관리자는 도면에 일정한 간격으로 세로 안내선을 그어 모든 센서가 안내선 위에 놓이도록 하려 한다. 안내선의 간격을 양의 정수 W로 정하면, 관리자는 정수 R을 하나 선택하여 좌표 R+t×W마다 안내선을 그린다. 여기서 t는 음수, 0, 양수를 모두 포함하는 임의의 정수다. 즉, 도면의 양쪽 방향으로 같은 간격의 안내선이 계속 이어진다고 생각한다. R은 반드시 0 이상 W 미만이어야 한다. 모든 재배 줄에는 동일한 W와 R을 사용하며, 줄마다 안내선의 시작 위치를 따로 바꿀 수 없다. 좌표가 A인 센서가 안내선 위에 있다는 것은 A=R+t×W를 만족하는 정수 t가 존재한다는 뜻이다. 센서가 없는 곳에 안내선이 생기는 것은 허용한다. 센서의 위치나 줄의 순서를 바꾸는 것은 허용하지 않는다. 또한 입력에 같은 좌표가 여러 번 등장하더라도 각각의 센서를 모두 안내선 위에 놓을 수 있어야 한다. 너무 촘촘한 안내선은 도면을 읽기 어렵게 만든다. 따라서 관리자는 모든 센서를 안내선 위에 놓을 수 있는 간격 중 가장 큰 것을 선택하려 한다. 다만 도면 출력 장치가 허용하는 간격의 상한이 B이므로 W는 B 이하여야 한다. 모든 센서의 좌표가 같은 경우에도 이 상한은 적용된다. 센서의 좌표와 B가 주어질 때 선택할 간격 W를 구하는 프로그램을 작성한다. 간격 1은 항상 사용할 수 있으므로 답이 없는 경우는 발생하지 않는다. 안내선의 시작 위치 R은 출력하지 않는다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. 1≤N≤30,000이고, 1≤B≤1,000,000,000이다.
둘째 줄에 센서의 좌표를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 0≤A_i≤1,000,000,000이다. 좌표는 정렬되어 있지 않을 수 있으며 중복될 수 있다.

출력

모든 센서를 안내선 위에 놓을 수 있는 간격 중 B 이하인 가장 큰 양의 정수 W를 한 줄에 출력한다.

4 20
14 38 62 86

12

3 50
7 7 7

50

3 8
65 5 35

6

출처: Devin.KR 자체 제작