호텔의 단체 객실 배정

문제

한 호텔에 단체 손님 N명이 도착했다. 호텔은 이번 단체를 위해 사용할 수 있는 객실 R개를 확보했으며, 각 객실에는 최대 C명까지 머물 수 있다. 확보한 객실의 수용 인원은 모두 같고, 다른 손님과 객실을 함께 쓰는 일은 없다. 담당자는 단체 손님 전원을 다음 규칙에 따라 배정하려 한다. 사용하는 모든 객실에는 같은 수의 손님을 배정해야 한다. 어떤 객실에 두 명을 배정했다면 사용하는 다른 객실에도 반드시 두 명씩 배정해야 한다. 손님이 한 명도 없는 객실은 사용한 객실로 세지 않는다. 확보한 객실을 전부 사용할 필요는 없지만, 사용하는 객실의 수가 R개를 넘을 수는 없다. 또한 한 객실에 배정하는 손님 수는 1명 이상 C명 이하여야 한다. 모든 손님은 정확히 하나의 객실에 배정되어야 한다. 일부 손님을 배정하지 않거나, 같은 손님을 여러 객실에 중복해서 세는 것은 허용되지 않는다. 따라서 객실마다 배정할 인원을 정했을 때 N명을 남김없이 같은 크기의 무리로 나눌 수 있어야 한다. 객실에 남는 침대가 있어도 괜찮지만, 객실별로 실제 배정된 손님의 수가 달라서는 안 된다. 호텔은 청소할 객실의 수를 줄이기 위해 가능한 배정 중 사용하는 객실의 수가 가장 적은 배정을 선택한다. 이는 객실마다 배정하는 손님의 수를 가능한 한 크게 정하는 것과 같다. 객실 자체의 번호나 손님 개인의 배정 순서는 결과에 영향을 주지 않으므로 출력하지 않는다. 사용하는 객실의 수가 정해지면 객실마다 배정할 인원도 하나로 정해진다. 규칙에 맞는 배정이 가능하면 객실마다 배정할 인원과 사용하는 객실의 수를 구한다. 확보한 객실 수와 객실당 수용 인원이 충분해 보이더라도 모든 객실의 배정 인원을 같게 만들 수 없다면 배정은 불가능하다. 가능한 배정이 하나도 없으면 -1을 출력한다.

입력

첫째 줄에 N, R, C가 공백으로 구분되어 주어진다.
N은 단체 손님의 수, R은 사용할 수 있는 객실의 수, C는 객실 하나의 최대 수용 인원이다.
N, R, C는 모두 1 이상 100,000 이하의 정수다.

출력

배정이 가능하면 객실마다 배정할 인원과 사용하는 객실의 수를 공백으로 구분하여 한 줄에 출력한다. 사용하는 객실의 수가 최소인 배정을 출력해야 한다. 배정이 불가능하면 -1을 한 줄에 출력한다.

72 15 10

9 8

35 6 6

-1

1 1 1

1 1

출처: Devin.KR 자체 제작