서버 기록의 공통 눈금

문제

게임 서버는 여러 구역에서 받은 사건 기록을 하나의 시간표에 표시하려고 한다. 각 사건에는 서버 가동 이후 경과한 시간이 정수로 적혀 있다. 같은 시각에 여러 사건이 발생할 수 있으며, 사건 기록은 시간순으로 주어지지 않을 수도 있다. 시간표 담당자는 사건 사이의 상대적인 시간 간격을 유지하면서, 모든 사건을 일정한 간격의 눈금 위에 놓으려고 한다. 눈금의 간격을 양의 정수 D라고 하자. 담당자는 정수 R을 하나 골라 눈금이 표시되는 시각을 R+qD로 정한다. 여기서 q는 음수, 0, 양수를 모두 포함하는 임의의 정수다. 즉, 눈금은 시간표의 양쪽 방향으로 같은 간격마다 이어진다. R은 모든 사건에 공통으로 적용하며, 사건마다 다른 R을 사용할 수는 없다. 눈금 자체가 음수 시각에 놓이는 것은 허용하지만, 입력으로 주어지는 사건 시각은 모두 0 이상이다. 어떤 D를 사용할 수 있으려면, 모든 사건의 시각이 이 눈금 중 하나와 정확히 일치하도록 하는 정수 R이 존재해야 한다. 눈금에 사건이 하나도 없는 구간이 있어도 괜찮으며, 한 눈금에 여러 사건이 겹쳐도 괜찮다. 사건 시각을 반올림하거나 사건을 시간표에서 제외하는 것은 허용하지 않는다. 또한 표시 장치의 설정 제한 때문에 D는 주어진 양의 정수 K 이하여야 한다. 조건을 만족하는 D 중 가장 큰 값을 구하는 프로그램을 작성한다. R이나 각 사건이 놓인 눈금 번호는 출력하지 않는다. 사건이 하나뿐이거나 모든 사건의 시각이 같을 때에도 같은 규칙을 적용한다. D가 1이면 모든 정수 시각을 눈금 위에 놓을 수 있으므로 답은 항상 존재한다. 가장 큰 D라는 정수 값만 구하므로 별도의 동점 처리는 필요하지 않다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1≤N≤30,000이고 1≤K≤1,000,000,000이다.
둘째 줄에 N개 사건의 시각 T_1, …, T_N이 공백으로 주어진다. 모든 T_i는 정수이며 0≤T_i≤1,000,000,000이다.

출력

모든 사건을 공통 눈금 위에 놓을 수 있는 간격 D 중 K 이하인 가장 큰 값을 정수 하나로 출력한다.

4 8
17 41 65 89

8

3 7
5 23 41

6

3 100
12 12 12

100

출처: Devin.KR 자체 제작