등차수열 복원

구간 [A,B]에 있는 K개의 수가 주어질 때, 그 수들만을 배수로 갖는 가장 작은 양의 공차 집합을 찾는다.

어려움8정수론수학그리디정렬아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

미르코는 유한소수로 나타낼 수 있는 실수 NN개를 종이에 적었다. 이어서 각 수마다 0에서 시작하고 그 수를 공차로 하는 등차수열을 적었다. 어떤 수가 xx이면 그 수열은 0,x,2x,3x,4x,0, x, 2x, 3x, 4x, \ldots 이다.

다른 종이에는 이렇게 만든 등차수열 NN개의 항 가운데 구간 [A,B][A, B]에 들어가는 값을 모두 모아, 중복을 지우고 오름차순으로 적었다. 다음 날 미르코는 첫 번째 종이를 잃어버렸다. 두 번째 종이만 보고 처음에 적은 수를 복원하자.

어떤 수의 집합이 조건을 만족하려면, 그 집합의 각 수로 만든 등차수열의 항 가운데 [A,B][A, B]에 들어가는 값을 모두 모았을 때 두 번째 종이의 KK개의 수와 정확히 같아야 한다.

입력

첫째 줄에 두 번째 종이에 적힌 수의 개수 KK가 주어진다. (1K501 \le K \le 50)

둘째 줄에 두 정수 AABB가 주어진다. (1A<B1061 \le A < B \le 10^6)

다음 KK개 줄에 두 번째 종이의 수가 한 줄에 하나씩 오름차순으로 주어진다. 각 수는 양수이고, [A,B][A, B]에 들어가며, 소수점 아래 자릿수가 5 이하다.

미르코가 처음에 적은 수도 모두 양수이고 소수점 아래 자릿수가 5 이하다. 조건을 만족하는 집합이 적어도 하나 있는 입력만 주어진다.

출력

조건을 만족하는 집합 가운데 원소 개수 NN이 가장 작은 것을 골라, 그 수를 오름차순으로 한 줄에 하나씩 NN개 줄에 출력한다. 각 수는 소수점 아래 다섯 자리까지 출력한다.

원소 개수가 가장 작은 집합이 여러 개면 사전순으로 가장 앞서는 것을 출력한다. 두 집합은 각각 오름차순으로 나열한 뒤 처음으로 달라지는 자리를 비교해서, 그 자리의 수가 더 작은 쪽이 앞선다.