시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 170 17 15 11.719%

문제

크기가 같은 정육면체 모양의 돌을 많이 가지고 있다면, 피라미드를 쉽게 만들 수 있다. 제일 밑에는 10*10개를 정사각형 모양으로 놓는다. 그 위에는 9*9개를 놓는다. 이런식으로 계속 쌓는다면, 가장 위에는 1개만 놓을 수 있다. 이렇게 쌓은 피라미드의 높이는 가장 밑의 길이와 같고, 앞에서 설명한 피라미드의 높이는 10이다. 이런 피라미드를 높은 피라미드라고 한다.

만약, 높은 피라미드가 너무 가파르다고 생각된다면, 다음과 같이 피라미드를 만들 수 있다. 제일 밑에는 10*10개를 정사각형 모양으로 놓는다. 그 위에는 8*8개를 놓고, 그 위에는 6*6개, 그 위에는 4*4개, 제일 위에는 2*2개를 놓는다. (만약, 가장 밑을 홀수 길이로 한다면, 제일 위에는 정육면체 1개만 놓을 수 있다) 이렇게 쌓은 피라미드의 높이는 밑의 길이의 절반과 같고, 이러한 피라미드를 낮은 피라미드라고 한다.

아주 아주 오래전에, 아버지로부터 엄청나게 많은 정육면체 모양의 돌을 상속받은 파라오가 있었다. 그는 이 돌을 모두 이용해서 피라미드를 만들라고 지시했다.

피라미드의 설계자는 돌의 개수에 따라 만들 수 있는 피라미드가 달라진다고 설명했다. 예를 들어, 10개가 있을 때는 밑이 3개인 낮은 피라미드를 만들 수 있고, 5개가 있을 때는 밑이 2개인 높은 피라미드를 만들 수 있다. 하지만, 7개가 있을 때는 모두 사용해서 만들 수 있는 피라미드가 없다.

이 사실을 들은 파라오는 크게 분노하였다. 그는 몇일동안 생각한 뒤에 다음과 같은 조건을 제시했다.

1. 모든 돌을 사용해야 한다.

2. 피라미드를 하나 이상 만들 수 있다. 하지만, 가능한 적게 만들어야 한다.

3. 같은 모양의 피라미드는 하나만 만들 수 있다.

4. 각 피라미드의 높이는 적어도 2이다.

5. 위의 조건을 모두 지켰을 때, 가장 큰 피라미드(많은 돌을 사용한 피라미드)의 크기를 가능한 크게 만들어야 한다.

6. 위의 조건을 모두 지켰을 때, 두 번째로 큰 피라미드의 크기를 가능한 크게 만들어야 한다.

7. 5, 6번 조건과 같은 식으로 계속...

돌의 개수가 주어졌을 때, 파라오의 조건을 지켜서 피라미드를 어떻게 건설해야 하는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 돌의 개수 c가 주어진다. (1 ≤ c ≤ 106) 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 케이스 번호와 만들 피라미드를 출력한다. 피라미드는 큰 순서대로 차례대로 출력한다. 피라미드를 출력할 때는, 밑의 길이를 출력하고 낮은 피라미드인 경우에는 L을, 높은 피라미드인 경우에는 H를 출력한다. 만약, 돌의 개수가 같은 피라미드가 있다면, 높은 피라미드를 먼저 출력한다. 파라오의 조건을 지켜서 피라미드를 만들 수 없는 경우에는 "impossible"을 출력한다.

예제 출력 형식을 참고한다.

예제 입력

29
28
0

예제 출력

Case 1: 3H 3L 2H
Case 2: impossible

힌트

출처

ACM-ICPC > World Finals > 2011 World Finals J번