메뉴 건너뛰기

문제

00b03 요셉문제 (원형큐 사용하기) 4  

시간메모리제출 올바른 답 비율
1초64MB
887
371
41.8%


나의 횟수나의 최근 판정시도 성공 비율
257231
89.9%
요셉문제 (원형큐 사용하기) 

카메롯 성에서는 회의가 열리고 있다. 밤마다 용이 나타나서 백성들을 괴롭히기 때문이다. 원탁의 기사 모두가 용과 싸우고 싶어하지만 많은 군대를 이끌고 가면 용이 미리 알아채기 때문에 기사 한 명만이 갈 수 있다. 아더왕은 과연 누구를 보내야 하는가 고민에 빠졌다. 아더왕은 과연 누구를 보내야 하는가 고민에 빠졌다. 그러던 중 란슬러트가 묘안을 제시하였다.

원탁에 둘러앉아 있는 기사 n명에게 시계방향으로 차례대로 1번부터 n번의 번호를 부여한다. 다음 그 중 임의의 숫자 m을 선택하여 그 번호의 기사를 제외시킨다. 다음 그 기사로부터 시계 방향으로 k번째 있는 기사를 선택하여 제외시킨다. 이렇게 제외된 기사로부터 k번째 있는 기사를 제외시키는 작업을 단 한 명이 남을 때까지 계속한 뒤, 그 결과 마지막으로 나은 기사가 용과 싸우러 가는 것이다.

예를 들어, n=8, m=2, k=3인 경우, 2번 기사가 먼저 제외된 후, 이어 5번, 8번 기사가 차례대로 제외된다.

원탁의 기사의 n, 처음 선택한 기사의 번호 m, 다음으로 몇 번째 기사를 제외시킬 것인가 하는 k가 주어질 때, 제외되는 기사들의 번호를 순서대로 출력하고, 용과 싸우러 가게 되는 기사의 번호를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 n, m, k가 차례대로 공백을 사이에 두고 주어진다. 단, n<=1000 이고, m, k<=n 이다.

출력

첫째 줄에 제외되는 기사들의 번호를 제외되는 순서대로 출력하나다. 둘째 줄에 마지막까지 남아 용과 싸우러 가게 되는 기사의 번호를 출력한다.

예시
1입력
8 2 3
출력
2 5 8 4 1 7 3
6
위로