Split Windows

The Dotty Software Company makes software that runs on inexpensive text-based terminals. One of its applications has a main window that can be repeatedly subdivided into smaller subwindows. Given a description of the screen layout after a sequence of window splits, draw the minimum-sized window grid that is consistent with that description.

Here we care only about window boundaries, so every cell inside a window is left blank. Each window that is not further subdivided (an undivided window) has a label: a distinct uppercase letter. On a text terminal the boundaries are drawn with these characters:

• The uppercase letter label is placed in the upper-left corner of each undivided window.
• An asterisk * marks a window corner that has no label.
• A dash - marks upper and lower boundaries that are not corners.
• A vertical bar | marks side boundaries that are not corners.

For example, an application window could start with the single label M, then be split into a left and a right subwindow (adding label R), and finally the left subwindow could be split into a top and a bottom subwindow (adding label C). This produces Window 1 below.

Every split pattern can be described by a binary tree of characters:

• An undivided rectangular window has one uppercase label; its tree is just that label.
• A window may be split into left and right subwindows, or into top and bottom subwindows. The corresponding tree has as its root the split's boundary character: a vertical bar | for a left/right split, or a dash - for a top/bottom split. For a left/right split the root's left and right subtrees are the left and right subwindows; for a top/bottom split they are the top and bottom subwindows.

A tree can be written more compactly by its preorder traversal:

• The preorder traversal of a single-node tree (one letter) is that letter.
• The preorder traversal of a tree with a left and a right subtree is the root character (- or |), followed by the preorder traversal of the left subtree, then the preorder traversal of the right subtree.

Trees 1-4 below are consistent with Windows 1-4; note that Tree 4 contains Trees 2 and 3. Their preorder traversals are:

|-MCR
-|-ABC-D|E-FG
-P-|Q|RST
|-|-ABC-D|E-FG-P-|Q|RST

Every undivided window must have room for at least one character inside, so every split tree has an associated minimum window size. Windows 1-4 are the minimum-sized windows for Trees 1-4. Even in a minimum-sized window, not every undivided window contains only one character.

For size calculations it helps to imagine that a window contains its interior plus a half-character-wide boundary on all four sides, so a window's total dimensions are one larger than its interior dimensions. Because a window must hold at least one interior character, its minimum total size is $2 \times 2$. With this definition, the widths of a left and a right subwindow add up to the width of the window that encloses them, and the heights of a top and a bottom subwindow add up to the height of their enclosing window.

When an enclosing window must be stretched, its subwindows grow in proportion to their minimum sizes. Let $D$ be the stretched size of the combined window along the split direction, let $d$ be its minimum size (the sum of the two subwindows' minimum sizes), and let $d_1$ and $d_2$ be the two subwindows' minimum sizes. In proportion, the stretched sizes would be $D_1 = d_1 \times (D/d)$ and $D_2 = d_2 \times (D/d)$. When these are not integers, the top or left subwindow is always the one rounded up to the next integer, so $D_1 = \lceil d_1 \times D / d \rceil$ and $D_2 = D - D_1$. The final size of an enclosing window is always fixed before the final sizes of its subwindows.

For example, a window stretched to height $10$ and split into a top of minimum height $2$ and a bottom of minimum height $4$ has $d = 6$, so $D_1 = 2 \times (10/6) = 3.33\ldots$ rounds up to $4$ and $D_2 = 6$. If every horizontal and vertical split were interchanged, the same rule would apportion widths instead of heights.

The first line of input contains one integer, the number of preorder traversals that describe window structures. Each of the following lines contains one preorder traversal. Each traversal consists of the dividers | and - together with 1 to 26 uppercase letters.

For each preorder traversal, first print the traversal's number (starting at 1) on its own line, then print the minimum-sized window grid that the traversal represents. Unlike the usual contest output conventions, a line of this output may contain two or more consecutive blanks. Every output grid has at most 53 rows and at most 53 columns.