P12900 [NERC 2020] ASCII Automata Art

This problem statement is quite wordy by itself and does not need a legend. You are given a regular expression and your task is to render its corresponding automaton as an ASCII art text drawing following the specification in the problem statement. Please, see examples. A regular expression in this problem consists of uppercase letters from `A` to `Z`, special characters `+`, `?`, `*`, and parenthesis that are used for grouping. An input to the problem is given by an `` non-terminal of the following BNF grammar: ``` ::= ::= | `|' ::= | | ::= | `(' `)' | `+' | `?' | `*' ::= `A' | `B' | ... | `Z' ``` A regular expression is rendered as an ASCII art picture using the precise rules that are given below. They recursively define a unique representation for each regular expression as a rectangular *box* of characters with the specified number of rows and columns. Empty characters of the representation, including trailing ones, must be filled with spaces. A `` that consists of a sequence of $n$ uppercase letters is rendered as a box of 3 rows and $4 + n$ columns using `+` and `-` characters to render a border on the first and the last rows and columns as shown in the example. The production rule for the `` non-terminal in the grammar is intentionally ambiguous. The longest possible sequence of adjacent `` non-terminals in the regular expression must be grouped into a `` and rendered as a single box. For example, a `` of `NERC` is rendered as the following $3 \times 8$ box: ``` +------+ + NERC + +------+ ``` A `` that consists of a sequence of `` non-terminals and `` non-terminals with letters (as described above) is rendered by laying out the constituent boxes left-to-right, aligned vertically to the top, with 2 columns separating adjacent boxes. The height of the resulting box is equal to the maximum height of the constituent boxes. Each pair of adjacent boxes is joined by rendering `->` characters on the 2nd row in the columns between them. For example, a `` of `N(E)RC` (consisting of a sequence: `` of `A`, `` of `(E)`, and a letters-only `` of `RC`) is rendered as the following $3 \times 20$ box: ``` +---+ +---+ +----+ + N +->+ E +->+ RC + +---+ +---+ +----+ ``` An `` that consists of a single `` is rendered as its ``. An `` that consists of a `|`-separated sequence of `` non-literals is rendered by laying out the corresponding `` boxes top-to-bottom, aligned to the left, with a single row separating adjacent `` boxes. The width of the resulting box is equal to the maximum width of the `` boxes plus 6. There are 3 additional columns on the left, and 3 on the right. The first column and the last column use `+` and `|` characters to join the 2nd rows of all the `` boxes from the top to the bottom one, with `+` placed on the 2nd row of each `` box. The 2nd and the 3rd columns on the left and the 3rd-to-last and the 2nd-to-last columns on the right have `->` characters on the 2nd rows of the corresponding `` boxes. Additionally, shorter `` boxes are connected on the right with extra `-` characters on their 2nd rows. For example, an `` of `C|ON|TEST` is rendered as the following $11 \times 14$ box: ``` +---+ +->+ C +---->+ | +---+ | | | | +----+ | +->+ ON +--->+ | +----+ | | | | +------+ | +->+ TEST +->+ +------+ ``` An `` of `(` `` `)` is rendered as its ``. An `` of `` `+` is rendered as a box of its source `` with 2 additional rows at the bottom and 6 additional columns (3 on the left and 3 on the right). The first and the last columns, starting with the 2nd row, and the last row are filled with the connecting characters as shown in the example. - The 2nd row starts with `+->` and ends with `->+` to connect to the 2nd row of the source `` box. - The last row starts with `++ A +->+ | +---+ | | | ++` to represent an epsilon-edge in the corresponding automaton. - The 5th row starts with `+->` and ends with `->+` to connect to the 2nd row of the source `` box. For example, an `` of `B?` is rendered as the following $6 \times 11$ box. ``` +-------->+ | | | +---+ | +->+ B +->+ +---+ ``` An `` of `` `*` is rendered as a box of its source `` with 5 additional rows (3 at the top and 2 at the bottom) and 6 additional columns (3 on the left and 3 on the right). The first and the last columns, with the 2nd and the last row, are filled with the connecting characters as shown in the example. - The first row of `` `*` is always empty (filled with spaces). - The 2nd row ends with `->+` to represent an epsilon-edge in the corresponding automaton. - The 5th row starts with `+->` and ends with `->+` to connect to the 2nd row of the source `` box. - The last row starts with `++ | | | +---+ | +->+ C +->+ | +---+ | | | +` to represent the starting state of the automaton and ends with `->F` to represent the final state of the automaton. See the example output.

The input consists of a single line that corresponds to the $\langle input \rangle$ non-terminal of the grammar given the problem statement and has at most 100 characters in length.

On the first line of the output, write two integers $h$ and $w$ --- the height and the width, correspondingly, of the $h \times w$ box that corresponds to the given $\langle input \rangle$. On each of the next $h$ lines, write $w$ characters of the corresponding ASCII art rendering.