Quad Tree

While searching for treasure at an ancient Aztec ruin, Hanshin found a papyrus scroll covered with a long text. The text was made of only three kinds of characters: $B$, $W$, and $Q$.

Having studied a little cryptography, Hanshin recognized this as a famous 3000-year-old quad tree encoding.

Quad tree encoding compresses a picture (such as a treasure map) with the following rules:

• If the whole picture is black, encode it as $B$.
• If the whole picture is white, encode it as $W$.
• If it contains both black and white parts, encode it as $Qxxxx$: recursively split the picture into four parts in the order top-left, top-right, bottom-left, bottom-right, and encode each part ($x$) again.

Every picture is an $n \times n$ square of pixels where $n$ is a power of two, and it is always encoded as a perfect quad tree.

For example, a $2 \times 2$ checkerboard is written as $QWBBW$, and a $4 \times 4$ checkerboard is written as $QQWBBWQWBBWQWBBWQWBBW$.

Write a program that decodes such a quad tree string into an XBM-format file.

The first line contains an integer $n$ ($8 \le n \le 512$), the width and height of the picture in pixels; $n$ is always a power of two.

The second line contains a string of only $B$, $W$, and $Q$ that encodes the $n \times n$ picture as a quad tree.

Print the XBM file contents in the following format:

• Line 1: #define quadtree_width n, where $n$ is the width in pixels.
• Line 2: #define quadtree_height n, where $n$ is the height in pixels.
• Line 3: static char quadtree_bits[] = {
• The next $n$ lines: each row of the picture converted into $n/8$ hexadecimal values. Each hex value packs 8 pixels from left to right into an 8-bit number, where the leftmost pixel has bit value 1 and the rightmost pixel has bit value 128. A black pixel is 1 and a white pixel is 0. Write each value in the form 0xdd (two lowercase hex digits) and append a comma (,) after every value. For example, the 8 pixels $WBBBBWWB$ give $2 + 4 + 8 + 16 + 128 = 158$ = 0x9e.
• Last line: };