J. 피라미드

동일한 정육면체가 많이 있다면 피라미드를 쌓는 것은 그리 어렵지 않다. 평평한 기초 위에, 예컨대 \(10 \times 10\)개의 정육면체를 정사각형으로 놓는다. 그 정사각형 위 중앙에 \(9 \times 9\) 정사각형으로 정육면체를 놓는다. 이런 식으로 계속하면 맨 위에 정육면체 하나가 남는데, 이것이 피라미드의 꼭대기이다. 이런 피라미드의 높이는 밑변의 길이와 같으며, 이 경우 10이다. 이를 높은(high) 피라미드라고 부른다. 높은 피라미드가 너무 가파르다고 생각되면 다음과 같이 할 수 있다. \(10 \times 10\) 밑면 정사각형 위에 \(8 \times 8\) 정사각형을 놓고, 그다음 \(6 \times 6\) 정사각형을 놓는 식으로 하여 맨 위 \(2 \times 2\) 정사각형으로 끝낸다(밑변 길이가 홀수로 시작하면 물론 맨 위에 정육면체 하나가 남는다). 이 피라미드의 높이는 밑변 길이의 약 절반이다. 이를 낮은(low) 피라미드라고 부른다. 옛날 옛적에(사실 아주 오래전에) 아버지에게서 엄청난 수의 돌 정육면체를 물려받은 파라오가 있었다. 그는 건축가에게 이 정육면체를 단 하나도 남김없이 모두 사용해 피라미드를 지으라고 명령했다. 건축가는 모든 개수의 정육면체로 피라미드를 만들 수 있는 것은 아니라고 정중히 설명했다. 정육면체 10개로는 밑변 3인 낮은 피라미드를 지을 수 있다. 5개로는 밑변 2인 높은 피라미드를 지을 수 있다. 하지만 정확히 7개로는 어떤 피라미드도 지을 수 없다. 파라오는 언짢았지만, 고민 끝에 새로운 조건을 내놓았다. 1. 모든 정육면체를 사용해야 한다. 2. 피라미드를 여러 개 지어도 되지만, 가능한 한 적은 수의 피라미드를 지어야 한다. 3. 모든 피라미드는 서로 달라야 한다. 4. 각 피라미드의 높이는 2 이상이어야 한다. 5. 위 조건을 만족하면서, 가장 큰 피라미드가 가능한 한 커야 한다(즉, 가장 많은 정육면체를 포함해야 한다). 6. 위 조건을 만족하면서, 두 번째로 큰(ne\(xt-to-la\)rgest) 피라미드가 가능한 한 커야 한다. 7. 이런 식으로 계속... 모래 위에 도형과 그림을 그려 가며, 건축가는 꽤 오랜 시간이 걸려서야 최선의 답을 찾았다. 정육면체의 개수가 주어질 때 파라오의 조건을 만족하는 방법을 결정하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 한 줄로 주어진다. 테스트 케이스는 사용할 수 있는 정육면체의 수를 나타내는 정수 \(c\) (\(1 \le c \le 10^{6}\))이다. 마지막 테스트 케이스 다음에는 0 하나가 있는 줄이 주어진다.

각 테스트 케이스마다 케이스 번호와 함께 지어야 할 피라미드들을 출력한다. 피라미드는 큰 것부터 순서대로 출력한다. 각 피라미드는 밑변의 길이 뒤에 낮은 피라미드면 L, 높은 피라미드면 H를 붙여 나타낸다. 서로 다른 두 피라미드의 정육면체 수가 같으면 높은 피라미드를 먼저 출력한다. 파라오의 요구를 만족할 수 없으면 “impossible”을 출력한다. 샘플 출력의 형식을 따른다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2011