관측 시계의 공통 눈금

문제

산간 지역의 한 날씨 관측소는 여러 센서에서 도착한 측정 자료를 하나의 시간표에 모은다. 각 자료에는 관측소의 기준 시각부터 몇 초가 지났을 때 측정했는지를 나타내는 정수 시각이 붙어 있다. 센서가 같은 순간에 각각 자료를 보낼 수 있으므로 같은 시각이 여러 번 기록될 수 있다. 자료는 시각이 감소하지 않는 순서로 정리되어 있다. 관측소는 보관 화면에 사용할 일정한 간격의 시간 눈금을 정하려 한다. 눈금 간격 D는 양의 정수 초이며, 관리자가 정한 상한 M을 넘을 수 없다. 눈금의 시작 위치는 자유롭게 옮길 수 있다. 즉, 0 이상 D 미만인 정수 R을 하나 골라 모든 측정 시각 T가 D로 나누었을 때 같은 나머지 R을 갖도록 하면 해당 간격을 사용할 수 있다. 시각 0이 반드시 눈금에 놓일 필요는 없다. 모든 눈금에 측정 자료가 있어야 하는 것은 아니다. 어떤 두 측정 사이에 자료가 없는 눈금이 여러 개 있어도 괜찮다. 또한 같은 시각에 여러 자료가 있더라도 그 시각이 눈금 하나에 놓이면 해당 자료들의 조건을 모두 만족한다. 자료의 개수나 측정값은 간격 선택에 영향을 주지 않으며, 입력에는 시각만 주어진다. 예를 들어 두 측정 시각 사이의 차이가 선택한 간격의 정수 배수라면 두 시각은 같은 위치로 맞춘 눈금 위에 함께 놓일 수 있다. 관리자는 화면이 지나치게 촘촘해지지 않도록 사용할 수 있는 간격 가운데 가장 큰 값을 선택하려 한다. 모든 자료가 같은 시각에 기록된 경우에도 같은 규칙을 적용하며, 이때는 상한까지의 모든 양의 정수 간격을 사용할 수 있다. 자료가 하나뿐인 경우도 마찬가지다. 간격 1은 어떤 정수 시각들이 주어져도 사용할 수 있으므로 답이 없는 경우는 발생하지 않는다. 시작 위치 R은 출력하지 않고, 조건을 만족하는 가장 큰 간격 D만 구한다.

입력

첫째 줄에 자료 수 N과 눈금 간격의 상한 M이 주어진다. 1 ≤ N ≤ 35,000이고 1 ≤ M ≤ 1,000,000,000이다.
둘째 줄에 정수 시각 T1, T2, …, TN이 공백으로 구분되어 주어진다. 0 ≤ T1 ≤ T2 ≤ … ≤ TN ≤ 1,000,000,000이다.

출력

모든 측정 시각이 같은 나머지를 갖도록 하는 양의 정수 D 중 M 이하인 최댓값을 출력한다.

4 10
5 29 65 89

6

3 100
17 17 17

100

3 20
2 9 17

1

출처: Devin.KR 자체 제작