쿼드 트리

고대 아즈텍 문명 유적지에서 보물을 찾던 한신이는 긴 문장이 적힌 파피루스 두루마리를 발견했다. 그 문장은 $B$, $W$, $Q$ 세 종류의 문자로만 이루어져 있었다.

암호학을 조금 배웠던 한신이는 이 문자열이 3000년 전에 만들어진 유명한 쿼드 트리(quad tree) 암호 구조라는 것을 알아냈다.

쿼드 트리 암호화는 그림(예를 들어 보물지도)을 다음 규칙으로 인코딩한다.

• 그림 전체가 검은색이면 $B$로 변환한다.
• 그림 전체가 흰색이면 $W$로 변환한다.
• 검은 부분과 흰 부분이 섞여 있으면 $Qxxxx$ 형식으로, 그림을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서의 네 부분으로 재귀적으로 쪼갠 뒤 각 부분($x$)을 다시 변환한다.

모든 그림은 $n \times n$ 픽셀의 정사각형이며, $n$은 2의 거듭제곱이고, 항상 완벽한 쿼드 트리 구조로 인코딩되어 있다.

예를 들어 $2 \times 2$ 체스판은 $QWBBW$로, $4 \times 4$ 체스판은 $QQWBBWQWBBWQWBBWQWBBW$로 나타낼 수 있다.

이 쿼드 트리 문자열을 XBM 형식 파일로 해독하는 프로그램을 작성하라.

첫째 줄에 정수 $n$ ($8 \le n \le 512$)이 주어진다. 이 값은 그림의 가로·세로 픽셀 크기이며, 항상 2의 거듭제곱이다.

둘째 줄에 $B$, $W$, $Q$로만 이루어진 문자열이 주어진다. 이 문자열은 $n \times n$ 픽셀 그림을 쿼드 트리 구조로 인코딩한 것이다.

다음 형식으로 XBM 파일 내용을 출력한다.

• 첫째 줄: #define quadtree_width n ($n$은 가로 픽셀 크기이다.)
• 둘째 줄: #define quadtree_height n ($n$은 세로 픽셀 크기이다.)
• 셋째 줄: static char quadtree_bits[] = {
• 이어지는 $n$개의 줄: 그림의 각 행을 $n/8$개의 16진수 값으로 변환하여 출력한다. 각 16진수 값은 8개의 픽셀을 왼쪽에서 오른쪽 순서로 담은 8비트 값이며, 가장 왼쪽 픽셀의 비트 값이 1이고 가장 오른쪽 픽셀의 비트 값이 128이다. 검은 픽셀은 1, 흰 픽셀은 0으로 둔다. 각 값은 0xdd 형식(두 자리 소문자 16진수)으로 쓰고, 각 값 뒤에 쉼표(,)를 붙인다. 예를 들어 8픽셀 $WBBBBWWB$는 $2 + 4 + 8 + 16 + 128 = 158$ = 0x9e이다.
• 마지막 줄: };