描述

多蒂软件公司（Dotty Software Company）开发的软件是在价格低廉的基于文本的终端上显示的。该系统的一个应用程序有一个主窗口，这个主窗口可以进一步细分为多个子窗口。你的任务是根据一系列窗口拆分后的屏幕布局描述，绘制出与该描述相符的最小尺寸的窗口网格。

在这个问题中，我们将专注于窗口的边界，因此窗口内部的所有字符都将留空。每个不再进一步细分的窗口都有一个标签。每个标签都是一个不同的大写字母。对于文本终端，窗口的边界必须使用以下字符绘制：每个未细分窗口的左上角放置一个大写字母标签。在没有标签的窗口角落处出现星号 *。在没有角落的上边界和下边界出现短横线 -。在没有角落的侧边边界出现竖线 |。

例如，下面的拆分序列将生成窗口 1：最初可能有一个标记为 M 的应用程序窗口，接下来将其拆分为左右子窗口，添加标签 R，并且左子窗口再拆分为上下子窗口，添加标签 C。

对于每一种拆分模式，都有一个由字符组成的二叉树可以描述它。窗口拆分和树结构是从最简单的情况开始一起描述的。

1. 一个窗口可以是一个未细分的矩形。这样的窗口有一个大写字母作为标签。该窗口对应的树只包含这个标签。
2. 一个窗口可以被拆分为左右子窗口，或者上下子窗口，相应的树的根节点是拆分的边界字符：分别是竖线 | 或短横线 -。根节点有左右子树，分别对应于上下子窗口或左右子窗口。

上面的树 1 和下面的树 2 - 4 将与窗口 1 - 4 相对应。请注意，树 4 包含树 2 和树 3。

这些树可以通过前序遍历更简洁地表示：

1. 对于只有一个节点（包含一个字母）的树，其前序遍历就是那个字母。
2. 对于有左右子树的树，其前序遍历是树的根节点的字符（- 或 |），后面跟着左子树的前序遍历，然后是右子树的前序遍历。

树 1 到树 4 的前序遍历分别是： |-MCR -|-ABC-D|E-FG -P-|Q|RST |-|-ABC-D|E-FG-P-|Q|RST

每个未细分的窗口内部必须至少有一个字符的空间。因此，每一个拆分树都将关联一个最小窗口尺寸。窗口 1 - 4 是树 1 - 4 对应的最小尺寸窗口。每个窗口都说明了这样一个事实，即即使在最小尺寸的窗口中，并非所有未细分的窗口都只包含一个字符。

考虑树 4 和窗口 4。主窗口被拆分为一个具有树 2 的左窗口和一个具有树 3 的右窗口。左窗口类似于窗口 2，但右窗口并不完全像窗口 3。左右子窗口的高度必须匹配，所以右窗口必须进行拉伸。

拉伸规则取决于窗口尺寸的定义。为了便于进行尺寸计算，最容易想象的是一个窗口包含其内部以及四周半字符宽的边界，所以一个窗口的总尺寸比其内部尺寸大 $1$。因此，一个窗口的最小尺寸是 $2×2$，因为一个窗口内部必须包含一个字符，并且我们为边界加上 $1$。这个定义也意味着左右子窗口的宽度之和等于它们所包含的窗口的宽度。上下子窗口的高度之和等于它们所包含的窗口的高度。

窗口 4 中的右窗口必须拉伸以匹配左窗口的高度 $10$。右窗口被拆分为一个具有树 P 的顶部子窗口（最小高度为 $2$）和一个具有树 -|Q|RST 的底部子窗口（最小高度为 $4$）。在拉伸窗口中的尺寸规则是，如果可能的话，子窗口的高度按其最小高度成比例扩展。这里一些符号可能会有所帮助：设 $D = 10$ 为组合拉伸窗口的高度。我们想要确定 $D_1$ 和 $D_2$，即顶部和底部子窗口的拉伸高度。称相应的最小尺寸为 $d = 6$，$d_1 = 2$，和 $d_2 = 4$。如果窗口从总高度 $d$ 按比例扩展到 $D$，我们将得到 $D_1 = d_1*(D/d) = 2*(10/6) = 3.333...$ 并且 $D_2 = d_2*(D/d) = 6.666....$。由于结果不是整数，我们将 $D_1$ 增加到 $4$ 并将 $D_2$ 减少到 $6$。

对于具有树 -|Q|RST 的底部窗口也有类似的计算。它进一步细分为一个具有树 |Q|RS 的顶部子窗口和一个具有树 T 的底部子窗口，每个子窗口的最小高度 $2 = d_1 = d_2$。高度需要相加等于 $D = 6$，所以它们按比例增加到 $D_1 = D_2 = 2*(6/4) = 3$（精确整数）。

一个包围窗口的最终尺寸总是在其子窗口的最终尺寸之前确定。在这个例子中只需要分配高度。如果在这个例子中所有的水平和垂直拆分都互换，生成一个树 -|-|ABC|D-E|FG|P|-Q-RST，那么宽度将相应地进行分配，如下面示例输出的第三部分所示。如果比例计算结果不是整数，总是将顶部或左子窗口的尺寸增加到下一个整数。

输入

输入的第一行包含一个整数，它是描述窗口结构的前序遍历的总数。这一行后面跟着每个前序遍历的一行内容。每个前序遍历将包含适当的分隔符 | 和 - 以及 $1$ 到 $26$ 个大写字母。

输出

对于每个前序遍历，在一行上打印前序遍历的编号，后面跟着该遍历可能表示的最小尺寸窗口网格。

输入示例

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

输出示例

1
M-R-*
| | |
C-* |
| | |
*-*-*
2
A-C-P-----*
| | |     |
B-* |     |
| | |     |
D-*-Q-R-S-*
|   | | | |
E-F-* | | |
| | T-*-*-*
| G-*     |
| | |     |
*-*-*-----*
3
A-B-D-E---*
| | | |   |
C-*-* F-G-*
|   | | | |
P---Q-*T*-*
|   |  |  |
|   R--*  |
|   |  |  |
|   S--*  |
|   |  |  |
*---*--*--*

来源

2001 年美国中中部地区竞赛