프랙타일 (Small)

문제

오래전 프랙탈 문명은 타일을 일렬로 늘어놓은 예술 작품을 만들었다. 타일은 금(G)과 납(L) 두 종류였다.

프랙탈 예술 작품은 두 매개변수로 정해진다. 하나는 타일 $K$ 개로 이루어진 원본 수열이고, 다른 하나는 복잡도 $C$ 이다. 원본 수열이 주어지면 복잡도가 1인 작품은 원본 수열 그 자체이고, 복잡도가 $X+1$ 인 작품은 복잡도가 $X$ 인 작품을 다음과 같이 바꾸어 얻는다.

복잡도 $X$ 인 작품의 각 L 타일을 원본 수열 하나로 바꾼다.
복잡도 $X$ 인 작품의 각 G 타일을 G 타일 $K$ 개로 바꾼다.

예를 들어 원본 수열이 LGL이면 복잡도가 1부터 3까지인 작품은 다음과 같다.

$C = 1$ : LGL (원본 수열 그 자체)
$C = 2$ : LGLGGGLGL
$C = 3$ : LGLGGGLGLGGGGGGGGGLGLGGGLGL

당신은 방금 프랙탈 예술 작품 하나를 발견했지만, 타일이 너무 더러워서 무엇으로 만들었는지 알아볼 수 없다. 이 지역의 프랙탈 문화를 잘 아는 고고학자로서 당신은 이 작품의 $K$ 와 $C$ 값은 알지만 원본 수열은 모른다. 금은 흥미로우니 작품에 G 타일이 적어도 하나 있는지 알고 싶다. 예산으로 대학원생 $S$ 명을 고용할 수 있다. 대학원생은 한 명당 작품의 타일 $K^C$ 개 가운데 당신이 고른 타일 하나를 닦아서 그 타일이 G인지 L인지 확인할 수 있다.

원본 수열이 무엇이었든 작품에 G 타일이 적어도 하나 있는지 확실히 알 수 있도록 닦을 타일을 $S$ 개 이하로 고를 수 있는가? 고를 수 있다면 어떤 타일을 닦아야 하는가?

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 세 개 $K$ , $C$ , $S$ 가 담긴 한 줄이다.

제한

$1 \le T \le 100$
$1 \le K \le 100$
$1 \le C \le 100$
$K^C \le 10^{18}$
$1 \le S \le K$

출력

각 테스트 케이스마다 Case #x: y 형식의 줄을 하나 출력한다. x는 1부터 시작하는 테스트 케이스 번호이다. 타일을 $S$ 개 이하로 골라서는 질문에 답할 수 없으면 y는 IMPOSSIBLE이고, 그렇지 않으면 y는 닦을 타일의 위치 목록이다. 타일 위치는 가장 왼쪽 타일을 1, 가장 오른쪽 타일을 $K^C$ 로 매긴다.

질문에 답할 수 있는 타일 집합은 여러 가지일 수 있으므로 다음 기준으로 하나를 정해 출력한다. 먼저 타일 수가 가장 적은 집합만 고려하고, 그중에서 위치를 오름차순으로 정렬한 목록이 사전순으로 가장 앞서는 집합을 고른다. 고른 집합의 위치를 오름차순으로, 공백 하나로 구분해 출력한다.

힌트

예제 1번에서 가능한 원본 수열은 GG, GL, LG, LL 네 가지이고, 각각 다음 작품을 만든다.

원본 수열 GG: GGGGGGGG
원본 수열 GL: GGGGGGGL
원본 수열 LG: LGGGGGGG
원본 수열 LL: LLLLLLLL

타일 2번만 보면 충분하다. 타일 2번이 G이면 작품에 G가 있다는 것을 확실히 안다. (원본 수열이 GG, GL, LG 중 무엇인지는 모르지만 상관없다.) 타일 2번이 L이면 원본 수열은 LL일 수밖에 없으므로 작품에 G가 없다.

타일 1번 하나로는 부족하다. 타일 1번이 L이면 원본 수열은 LG일 수도 있고 LL일 수도 있다. 앞의 경우에는 작품에 G가 있고 뒤의 경우에는 없다. 따라서 답은 2이다. 1 2도 질문에 답할 수 있지만 필요한 것보다 타일을 많이 쓰므로 출력해야 할 답이 아니다. 1 2 3은 타일을 너무 많이 쓰므로 아예 올바른 선택이 아니다.

예제 2번에서 작품은 G 또는 L 타일 하나뿐이다. 그 타일을 보면 작품에 G가 있는지 바로 알 수 있다.

예제 3번에서 작품은 GG, GL, LG, LL 중 하나이다. 타일은 하나만 볼 수 있는데, 어느 타일도 혼자서는 충분하지 않다. 타일 1번이 L이면 작품은 LG일 수도 있고 LL일 수도 있으므로 G가 있는지 알 수 없다. 타일 2번이 L이면 작품은 GL일 수도 있고 LL일 수도 있으므로 역시 알 수 없다.

예제 4번은 예제 3번과 같지만 타일을 하나 더 볼 수 있다. 이제는 작품 전체를 볼 수 있다.

예제 5번에서 가능한 원본 수열은 여덟 가지이고, 각각 다음 작품을 만든다.

원본 수열 GGG: GGGGGGGGG
원본 수열 GGL: GGGGGGGGL
원본 수열 GLG: GGGGLGGGG
원본 수열 GLL: GGGGLLGLL
원본 수열 LGG: LGGGGGGGG
원본 수열 LGL: LGLGGGLGL
원본 수열 LLG: LLGLLGGGG
원본 수열 LLL: LLLLLLLLL

어떤 타일도 하나만으로는 질문에 답할 수 없으므로 타일이 적어도 두 개 필요하다. 타일 1번과 6번을 보면 된다. 두 타일이 모두 L이면 작품은 전부 L이고, 그렇지 않으면 G가 적어도 하나 있다. 1 2는 안 된다. 두 타일이 모두 L이어도 원본 수열이 LLG일 가능성이 남기 때문이다. 2 6도 질문에 답할 수 있지만 목록 1 6이 사전순으로 더 앞서므로 답은 1 6이다.