생산 라인의 공용 운반함

문제

한 공장에는 같은 부품을 만드는 N개의 생산 라인이 있다. 각 라인은 하루 작업을 마치면 자신이 만든 부품을 운반함에 담아 다음 공정으로 보낸다. i번 라인이 오늘 만든 부품의 수는 A_i개이며, 모든 부품은 크기가 같아 어느 운반함에도 담을 수 있다. 공장은 관리의 편의를 위해 모든 라인에서 하나의 공통 운반함 규격을 사용하려고 한다. 운반함의 규격 K는 운반함 하나에 담는 부품의 수를 뜻하는 양의 정수다. 선택한 규격을 사용할 때는 모든 운반함을 정확히 K개의 부품으로 채워야 한다. 덜 채운 운반함을 보내거나 부품을 다음 날로 넘길 수는 없다. 또한 서로 다른 라인에서 만든 부품을 하나의 운반함에 섞을 수 없으므로, 각 라인의 생산량을 따로 나누어 담을 수 있어야 한다. 라인마다 사용하는 운반함의 개수는 달라도 된다. 운반 장치에는 크기 제한이 있다. 선택할 수 있는 규격은 L 이상 U 이하인 정수뿐이다. 공장은 이 범위 안에서 모든 라인의 부품을 남김없이 담을 수 있는 규격이 몇 개인지 알아보려고 한다. 가능한 규격을 모두 확인한 뒤에는 그중 가장 큰 규격으로 운반함을 주문할 예정이다. 가장 큰 규격을 선택하면 같은 생산량을 옮길 때 필요한 운반함의 총개수를 줄일 수 있다. 생산량이 같은 라인이 여러 개 있어도 입력에는 각각 기록되며, 모든 라인이 선택한 규격을 사용할 수 있어야 한다. 가능한 규격의 개수를 셀 때는 라인이나 운반함의 개수가 아니라 서로 다른 K의 값을 센다. 가능한 규격이 하나도 없으면 개수와 선택할 규격을 모두 0으로 기록한다. 오늘의 생산량과 운반 장치의 제한이 주어졌을 때, 가능한 규격의 개수와 그중 가장 큰 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, L, U가 공백으로 주어진다. 1≤N≤100,000, 1≤L≤U≤10^9이다.
둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 모든 i에 대해 1≤A_i≤10^9이다.

출력

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

3 2 10
24 36 60

4 6

4 4 20
14 35 21 49

1 7

2 5 9
18 30

1 6

출처: Devin.KR 자체 제작