텔레점프
시간 제한1초메모리 제한128 MB
1칸 이동권 a장, 2칸 이동권 b장, 3칸 이동권 c장이 있고 n = a+b+c+1일 때, 행성 0부터 n-1까지를 정확히 한 번씩 방문하면서 모든 이동권을 정확히 한 번씩 쓰는 경로를 출력한다.
문제
홍준이와 친구들은 2014년을 맞이해 개의 행성을 여행하려 한다. 행성에는 번부터 번까지 번호를 붙인다. 우주선 대신 사성(Sasung)과 부글(Boogle)이 공동 개발한 텔레점프 텔레포트 시스템으로 순간이동한다. 출발지는 번 행성이며, 마지막 행성은 어디든 된다.
텔레점프에는 세 종류의 티켓이 있다.
- 1번 티켓: 에서 또는 로 이동 ()
- 2번 티켓: 에서 또는 로 이동 ()
- 3번 티켓: 에서 또는 로 이동 ()
1번 티켓 장, 2번 티켓 장, 3번 티켓 장을 가지고 있으며 이다. 각 종류는 최소 3장 이상이므로 이다.
모든 행성을 정확히 한 번씩 방문하는 순서를 출력하라. 각 티켓은 정확히 한 번씩 쓰여야 한다.
입력
첫 줄에 테스트 케이스 수 ()가 주어진다.
각 테스트 케이스는 한 줄에 세 정수 , , ()가 주어지며, 이때 이다.
출력
각 테스트 케이스마다 한 줄에 개의 행성 번호를 공백으로 구분해 출력한다. 방문 순서는 번 행성에서 시작해야 한다.
해가 여러 개면 아무 순서나 출력해도 된다. 입력에는 항상 해가 존재한다.
힌트
티켓 길이가 3인 이동으로 큰 간격을 먼저 확보한 뒤, 남은 1·2번 티켓으로 아직 방문하지 않은 행성을 메운다. 일 때는 세 종류를 번갈아 쓰는 반복 패턴 하나로 전체를 덮을 수 있다.