Quad Tree

Treasure hunter Hanshin discovered that the treasure map he brought back from the ruins of the Aztec civilization is a fake. Furious, he plans to prank people by sending this fake map not only to himself but to others as well. But if just anyone could read the map easily, Hanshin would be in trouble. So let's help Hanshin encrypt the map!

The map is given in XBM format, and you must compress and encode it into a quad tree structure.

The input is a black-and-white image in XBM format, given as follows.

• Line 1: #define quadtree_width n — here $n$ is the image width in pixels. The image is a square of $n \times n$ pixels.
• Line 2: #define quadtree_height n — the image height in pixels, equal to the width $n$.
• Line 3: static char quadtree_bits[] = {
• The next $n$ lines: each line represents one row of the image; that row's pixel values are given as $n/8$ hexadecimal values.
  • Each hexadecimal value has 8 bits and represents 8 pixels from left to right. The leftmost pixel has bit value $1$, and the rightmost pixel has bit value $128$.
  • A black pixel (B) has its bit set (1); a white pixel (W) has its bit unset (0).
  • Each hexadecimal value is given in the form 0xdd, where each d is one of 0–9, a–f. The values are separated by commas (,).
  • For example, the 8 pixels WBBBBWWB are written as 0x9e (2 + 4 + 8 + 16 + 128 = 158 = 0x9e).
• Last line: };

$n$ is a power of two with $8 \le n \le 512$.

On the first line, print the image size $n$.

On the second line, print the string that encodes the image as a quad tree. The encoding is defined recursively as follows.

• If every pixel in the current square region has the same color, print that color as a single character: B if all pixels are black, W if all pixels are white.
• Otherwise, print Q, then split the region into four equal quadrants and recursively encode each one in the order top-left, top-right, bottom-left, bottom-right.

Starting from the whole image, apply this rule and print the resulting string on one line with no spaces.