Description

本题的题目描述本身已经足够详细，不需要额外的背景说明。给定一个正则表达式，你的任务是根据题目描述中的规范，将其对应的自动机以 ASCII 艺术的形式绘制出来。请参考示例。

本题中的正则表达式由大写字母 A 到 Z、特殊字符 +、?、* 以及用于分组的括号组成。问题的输入由以下 BNF 文法中的 <input> 非终结符给出：

<input> ::= <expr>

<expr> ::= <term> | <term> `|' <expr>

<term> ::= <atom> | <atom><term> | <term><atom>

<atom> ::= <letter> | `(' <expr> `)' | <atom> `+' | <atom> `?' | <atom> `*'

<letter> ::= `A' | `B' | ... | `Z'

正则表达式的 ASCII 艺术绘制遵循以下精确规则。这些规则递归地定义了每个正则表达式的唯一表示形式，即一个由字符组成的矩形框，具有指定的行数和列数。表示中的空白字符（包括尾随空格）必须用空格填充。

一个由 $n$ 个大写字母组成的 <term> 被绘制为一个 $3 \times (4 + n)$ 的框，使用 + 和 - 字符在第一行和最后一行以及第一列和最后一列绘制边框，如示例所示。文法中 <term> 非终结符的产生规则故意设计为歧义。正则表达式中相邻的 <letter> 非终结符的最长连续序列必须被分组为一个 <term>，并绘制为一个单独的框。例如，NERC 的 <term> 被绘制为以下 $3 \times 8$ 的框：

+------+
+ NERC +
+------+

一个由 <atom> 非终结符和字母组成的 <term> 非终结符（如上所述）组成的 <term>，通过将组成框从左到右排列，垂直对齐到顶部，相邻框之间用 2 列分隔。结果框的高度等于组成框的最大高度。每对相邻框通过在它们之间的列中在第二行绘制 -> 字符来连接。例如，N(E)RC 的 <term>（由序列 <atom> 的 N、<atom> 的 (E) 和仅由字母组成的 <term> 的 RC 组成）被绘制为以下 $3 \times 20$ 的框：

+---+  +---+  +----+
+ N +->+ E +->+ RC +
+---+  +---+  +----+

一个由单个 <term> 组成的 <expr> 被绘制为其 <term>。

一个由 | 分隔的 <term> 非终结符序列组成的 <expr>，通过将对应的 <term> 框从上到下排列，左对齐，相邻 <term> 框之间用一行分隔。结果框的宽度等于 <term> 框的最大宽度加 6。左侧有 3 列额外列，右侧有 3 列额外列。第一列和最后一列使用 + 和 | 字符将所有 <term> 框的第二行从顶部到底部连接起来，+ 放置在每个 <term> 框的第二行。左侧的第二列和第三列以及右侧的倒数第三列和倒数第二列在对应的 <term> 框的第二行有 -> 字符。此外，较短的 <term> 框在右侧用额外的 - 字符在其第二行连接。例如，C|ON|TEST 的 <expr> 被绘制为以下 $11 \times 14$ 的框：

   +---+         
+->+ C +---->+
|  +---+     |   
|            |   
|  +----+    |   
+->+ ON +--->+   
|  +----+    |   
|            |   
|  +------+  |   
+->+ TEST +->+   
   +------+

一个 ( <expr> ) 的 <atom> 被绘制为其 <expr>。

一个 <atom> + 的 <atom> 被绘制为其源 <atom> 的框，底部增加 2 行，左右各增加 3 列。从第二行开始的第一列和最后一列以及最后一行填充连接字符，如示例所示。

• 第二行以 +-> 开头，以 ->+ 结尾，连接到源 <atom> 框的第二行。
• 最后一行以 +<- 开头，表示自动机中的反向边。

例如，A+ 的 <atom> 被绘制为以下 $5 \times 11$ 的框：

   +---+      
+->+ A +->+
|  +---+  |   
|         |   
+<--------+

一个 <atom> ? 的 <atom> 被绘制为其源 <atom> 的框，顶部增加 3 行，左右各增加 3 列。从第二行到第五行的第一列和最后一列以及第二行填充连接字符，如示例所示。

• <atom> ? 的第一行始终为空（填充空格）。
• 第二行以 ->+ 结尾，表示对应自动机中的 epsilon 边。
• 第五行以 +-> 开头，以 ->+ 结尾，连接到源 <atom> 框的第二行。

例如，B? 的 <atom> 被绘制为以下 $6 \times 11$ 的框：

+-------->+
|         |   
|  +---+  |   
+->+ B +->+   
   +---+

一个 <atom> * 的 <atom> 被绘制为其源 <atom> 的框，顶部增加 3 行，底部增加 2 行，左右各增加 3 列。第一列和最后一列以及第二行和最后一行填充连接字符，如示例所示。

• <atom> * 的第一行始终为空（填充空格）。
• 第二行以 ->+ 结尾，表示对应自动机中的 epsilon 边。
• 第五行以 +-> 开头，以 ->+ 结尾，连接到源 <atom> 框的第二行。
• 最后一行以 +<- 开头，表示自动机中的反向边。

例如，C* 的 <atom> 被绘制为以下 $8 \times 11$ 的框：

                 
+-------->+
|         |   
|  +---+  |   
+->+ C +->+   
|  +---+  |   
|         |   
+<--------+

一个 <input> 被绘制为一个比对应 <expr> 框多 6 列的框，左侧和右侧各增加 3 列。第二行以 S-> 开头，表示自动机的起始状态，以 ->F 结尾，表示自动机的终止状态。参见示例输出。

Input Format

输入由一行组成，对应于题目描述中给出的文法中的 <input> 非终结符，长度不超过 100 个字符。

Output Format

输出的第一行写入两个整数 $h$ 和 $w$，分别对应于给定 <input> 的 $h \times w$ 框的高度和宽度。接下来的 $h$ 行每行写入 $w$ 个字符，表示对应的 ASCII 艺术绘制。

NE?(ER)C++|(IS)*?|(CHA((LL))ENGING)

23 57
      +---+               +----+        +---+            
S->+->+ N +->+-------->+->+ ER +->+->+->+ C +->+->+->+->F
   |  +---+  |         |  +----+  |  |  +---+  |  |  |   
   |         |  +---+  |          |  |         |  |  |   
   |         +->+ E +->+          |  +<--------+  |  |   
   |            +---+             |               |  |   
   |                              +<--------------+  |   
   |                                                 |   
   |                                                 |   
   +->+--------------->+---------------------------->+   
   |  |                |                             |   
   |  |                |                             |   
   |  +->+--------->+->+                             |   
   |     |          |                                |   
   |     |  +----+  |                                |   
   |     +->+ IS +->+                                |   
   |     |  +----+  |                                |   
   |     |          |                                |   
   |     +<---------+                                |   
   |                                                 |   
   |  +-----+  +----+  +--------+                    |   
   +->+ CHA +->+ LL +->+ ENGING +------------------->+   
      +-----+  +----+  +--------+