상영관의 안내 신호 간격

문제

한 영화관은 여러 상영관에서 사용할 안내 장치를 준비하고 있다. 각 상영관에는 영화가 시작된 뒤 관객에게 짧은 안내 신호를 보내는 장치가 있다. 영화관은 관리 편의를 위해 모든 장치에 같은 신호 간격을 설정하려 한다. 영화의 시작 시각은 상영관마다 달라도 되며, 각 장치는 자기 상영관의 영화 시작 시각을 기준으로 동작한다. 신호 간격을 정수 x초로 설정하면 장치는 영화 시작 순간부터 x초마다 신호를 보낸다. 즉, 시작 순간을 0초라고 할 때 0초, x초, 2x초, 3x초와 같은 시점에 신호가 발생한다. 영화가 끝나는 순간까지 장치가 동작하며, 종료 이후의 신호는 고려하지 않는다. 영화관이 원하는 조건은 모든 영화의 종료 순간에 신호가 정확히 발생하는 것이다. 영화 길이가 A초라면 어떤 양의 정수 k에 대해 A = kx여야 이 조건을 만족한다. 영화가 끝나기 전에 신호가 여러 번 발생해도 괜찮다. 또한 영화 길이가 신호 간격과 같아서 시작 순간과 종료 순간에만 신호가 발생하는 경우도 허용한다. 장치의 설정 범위 때문에 신호 간격 x는 L초 이상 R초 이하의 정수여야 한다. 양 끝값 L과 R도 설정 가능한 값에 포함한다. 서로 다른 두 정수 간격은 신호가 발생하는 시점 일부가 겹치더라도 서로 다른 설정으로 센다. 같은 길이의 영화가 여러 개 주어져도 모든 영화에 종료 신호 조건을 적용한다. N개 영화의 길이와 설정 범위가 주어진다. 모든 영화의 종료 순간에 신호가 발생하도록 설정할 수 있는 정수 간격의 개수를 구한다. 가능한 간격이 하나 이상이면 그중 가장 큰 간격도 함께 구한다. 가능한 간격이 없으면 정해진 형식에 따라 두 값 모두 0으로 출력한다.

입력

첫째 줄에 영화 수 N과 설정 범위의 양 끝값 L, R이 공백으로 구분되어 주어진다.
둘째 줄에 N개 영화의 길이 A_1, A_2, …, A_N이 초 단위로 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 30,000, 1 ≤ L ≤ R ≤ 1,000,000,000, 1 ≤ A_i ≤ 1,000,000,000이다.

출력

가능한 신호 간격의 개수와 그중 가장 큰 간격을 공백으로 구분하여 한 줄에 출력한다. 가능한 간격이 없으면 0 0을 출력한다.

3 2 12
48 72 120

6 12

2 7 10
18 30

0 0

1 9 9
81

1 9

출처: Devin.KR 자체 제작