충전소의 공통 점검 간격

문제

전기차 충전소에는 서로 다른 주기로 작동 상태를 기록하는 충전기 N대가 있다. 모든 충전기는 시각 0분에 함께 기록을 남긴다. i번 충전기의 기록 주기가 A_i분이면 이후에는 A_i분, 2A_i분, 3A_i분과 같이 A_i의 양의 정수배인 시각마다 기록을 남긴다. 기록 주기는 작업 중에 바뀌지 않는다. 관리자는 충전기들의 기록을 모으는 점검 작업을 별도로 설정하려 한다. 점검 간격을 정수 d분으로 정하면 점검은 시각 0분부터 시작하여 d분, 2d분, 3d분마다 이루어진다. 이때 모든 충전기가 기록을 남기는 모든 시각이 반드시 점검 시각에도 포함되어야 한다. 어떤 점검 시각에 새 기록을 남기는 충전기가 하나도 없는 것은 허용된다. 즉, 점검할 때마다 모든 충전기가 동시에 기록을 남길 필요는 없다. 예를 들어 기록 주기가 12분인 충전기 하나를 생각하면 점검 간격 3분은 그 충전기의 모든 기록 시각을 포함한다. 반면 점검 간격 5분은 시각 12분의 기록을 포함하지 못하므로 사용할 수 없다. 여러 충전기가 있으면 이 조건을 각각의 충전기에 모두 만족해야 한다. 충전기의 기록 시각을 앞뒤로 옮기거나 일부 기록을 건너뛰는 것은 허용되지 않는다. 관리자가 설정할 수 있는 점검 간격의 범위는 L분 이상 R분 이하이며, 양 끝값도 범위에 포함된다. 관리자는 조건을 만족하는 간격 중 가장 큰 값을 선택하여 불필요한 점검 횟수를 줄이려 한다. 가능한 간격이 여러 개여도 가장 큰 정수 하나만 답으로 사용한다. 범위 안에 조건을 만족하는 정수가 하나도 없다면 -1을 출력한다. 실제 기록 시각들을 끝없이 나열하지 않고, 주어진 주기들을 이용하여 선택할 간격을 구한다.

입력

첫째 줄에 충전기 수 N과 점검 간격의 하한 L, 상한 R이 공백으로 주어진다. 세 값은 정수이며 1≤N≤30,000, 1≤L≤R≤1,000,000,000이다.
둘째 줄에 각 충전기의 기록 주기인 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 모든 i에 대하여 1≤A_i≤1,000,000,000이다. 모든 시간의 단위는 분이다.

출력

모든 충전기의 모든 기록 시각을 포함할 수 있는 정수 점검 간격 중 L 이상 R 이하인 최댓값을 출력한다. 가능한 간격이 없으면 -1을 출력한다.

4 4 10
24 48 72 120

8

3 7 10
18 30 42

-1

1 12 20
36

18

출처: Devin.KR 자체 제작