냉찜질 압축

많은 디지털 이미지 압축 기법은 하나의 균일한 색으로 이루어진 영역을 찾아 기술하는 방식으로 동작한다. 아래는 흑백 이미지를 압축하는 간단한 방법이다(컴러로도 쉽게 확장된다). 핵심 아이디어는 각 부분 그림이 한 가지 색만 담을 때까지 그림을 세로 또는 가로로 반복해서 둘로 나누는 것이다.

직사각형 이미지는 다음과 같이 정의되는 압축 표현식(compression-expression) 으로 기술한다. 모든 압축 표현식은 2비트짜리 태그로 시작하며, 태그 값에 따라 뒤에 압축 표현식이 더 이어질 수 있다.

• 00 — 전부 검은색 픽셀로 이루어진 정사각형 영역. 문맥에 따라 이 정사각형은 1픽셀, $2\times2$, $3\times3$ 등 어떤 크기든 될 수 있다.
• 11 — 전부 흰색 픽셀로 이루어진 정사각형 영역. 마찬가지로 문맥에 따라 크기가 정해진다.
• 10 — 가로 분할. 뒤에 두 개의 압축 표현식이 이어진다. 첫 번째 그림을 왼쪽에, 두 번째 그림을 오른쪽에 나란히 놓아 완성한다. 가로 분할은 두 그림의 높이가 같을 때만 가능하다.
• 01 — 세로 분할. 뒤에 두 개의 압축 표현식이 이어진다. 첫 번째 그림을 위에, 두 번째 그림을 아래에 놓아 완성한다. 세로 분할은 두 그림의 너비가 같을 때만 가능하다.

분할을 해석할 때, 두 구성 요소가 공유하는 변(가로 분할은 높이, 세로 분할은 너비)가 서로 일치하도록 크기를 다시 조정해야 할 수 있다. 예를 들어 $2\times6$ 그림 $A$(너비 2, 높이 6)와 $3\times4$ 그림 $B$가 있을 때:

• 세로 분할은 $A$를 3배($6\times18$), $B$를 2배($6\times8$)로 키워야만 가능하며, 합쳐진 그림은 $6\times26$이 된다.
• 가로 분할은 $A$를 2배($4\times12$), $B$를 3배($9\times12$)로 키워야만 가능하며, 합쳐진 그림은 $13\times12$가 된다.

검은 픽셀을 X, 흰 픽셀을 공백으로 나타내면, 표현식 00은 다음 그림을 뜻한다.

---
|X|
---

그리고 표현식 1000010011은 다음을 뜻한다.

-----
|XXX|
|XX |
-----

임의의 압축 표현식에는 그것이 나타낼 수 있는 가장 작은 그림이 유일하게 존재한다. 같은 표현식은 그 크기의 2배, 3배 등의 그림도 나타낼 수 있다.

입력의 각 줄에는 압축 표현식이 하나씩 주어진다. 각 표현식은 임의 개수의 0과 1로 이루어진 한 줄이다. 입력은 파일의 끝까지 계속된다.

입력으로 주어지는 모든 표현식은 유효한 압축 표현식이다.

각 입력 표현식에 대해, 그 표현식이 나타내는 가장 작은 흑백 그림을 출력한다. 검은 픽셀은 X로, 흰 픽셀은 공백으로 그리며, 위 예시처럼 -와 | 문자로 테두리를 두른다. 각 줄을 끝맺는 줄바꿈을 제외하고는, 테두리 밖에 어떤 문자나 공백도 출력해서는 안 된다.

출력에는 빈 줄이 있어서는 안 된다.