쿼드 트리

보물 사냥꾼 한신이는 아즈텍 문명의 유적지에서 가져온 보물 지도가 가짜라는 것을 알게 되었다. 화가 난 한신이는 자신뿐 아니라 다른 사람들에게도 이 가짜 지도를 보내 장난을 칠 계획을 세운다. 하지만 이 지도를 아무나 쉽게 읽을 수 있다면 한신이가 곤란해진다. 그러니 한신이를 도와 지도를 암호화해 주자!

지도는 XBM 형식으로 주어지며, 이를 쿼드 트리(quad tree) 구조로 압축·암호화하여 출력해야 한다.

입력은 XBM 형식의 흑백 이미지이며, 다음과 같은 형식으로 주어진다.

• 첫 번째 줄: #define quadtree_width n — 여기서 $n$은 이미지의 가로 픽셀 크기이다. 이미지는 $n \times n$ 픽셀의 정사각형이다.
• 두 번째 줄: #define quadtree_height n — 세로 픽셀 크기이며, 가로와 같은 $n$이다.
• 세 번째 줄: static char quadtree_bits[] = {
• 이어지는 $n$개의 줄: 각 줄은 이미지의 한 행을 나타내며, 그 행의 픽셀 값이 $n/8$개의 16진수 값으로 변환되어 주어진다.
  • 각 16진수 값은 8비트로, 8개의 픽셀을 왼쪽에서 오른쪽 순서로 나타낸다. 가장 왼쪽 픽셀의 비트 값은 $1$이고, 가장 오른쪽 픽셀의 비트 값은 $128$이다.
  • 검은색 픽셀(B)은 비트가 켜져 있고(1), 흰색 픽셀(W)은 비트가 꺼져 있다(0).
  • 각 16진수 값은 0xdd 형식으로 주어지며, 여기서 d는 0–9, a–f 중 하나이다. 값들은 쉼표(,)로 구분된다.
  • 예를 들어, 8개의 픽셀 WBBBBWWB는 0x9e로 표기된다 (2 + 4 + 8 + 16 + 128 = 158 = 0x9e).
• 마지막 줄: };

$n$은 $8 \le n \le 512$를 만족하는 2의 거듭제곱이다.

첫 번째 줄에 이미지의 크기 $n$을 출력한다.

두 번째 줄에 이미지를 쿼드 트리 구조로 암호화한 문자열을 출력한다. 암호화는 다음 규칙에 따라 재귀적으로 이루어진다.

• 현재 정사각형 영역의 모든 픽셀이 같은 색이면, 그 색을 한 글자로 출력한다. 모두 검은색이면 B, 모두 흰색이면 W.
• 색이 섞여 있으면 Q를 출력한 뒤, 영역을 같은 크기의 네 사분면으로 나누어 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 각각을 같은 방법으로 재귀적으로 암호화한다.

전체 이미지에서 시작하여 이 규칙을 적용한 결과 문자열을 공백 없이 한 줄로 출력한다.