题目内容

IP 场景下，操控装置要靠下发配置语句来完成；装置随附的说明书会给它能够执行的每一条语句写明写法。写法本身得贴合下列表格里列出的那些约束。

补充约定：

1.关键字、成组括号、分支竖线彼此之间要用单个空格切开。除开括号与分支竖线 $|$ 这两类记号，其余一律当成关键字

2.单条语句的长度上限为 $1000$ 个字符。

以下给出若干合法写法的示范：

1.a b { c | d c }
2.a b [ { c | d c } ]
3.a c { c | b { c e | d c } [ c b ] }

假定说明书里的写法均已核验无误，并且关键字、竖线、括号两侧均已插入空格。请清点某一条写法里，各个必填关键字最少得登场几次。

输入描述

读入的文本即某条语句的写法；该写法均已核验无误，并且关键字、竖线、括号两侧均已插入空格。眼下不必处理非法写法，例如 $d\ k\ r$ { $a | d$} 这种。

输出描述

结果占两行：上一行列出必填关键字，依字母顺序排好，彼此空一格；下一行给出与上一行各位置对应的最少登场次数，同样彼此空一格。

样例1

输入

a b { c | d c }

输出

a b c
1 1 1

说明

花括号{}代表必填段，该段内存在 $2$ 条岔路，两条岔路都含 $c$，故 $c$ 不能不写，且次数等于 $1$ 。

样例2

输入

a b [ { c | d c } ]

输出

a b
1 1

说明

末尾方括号是可省略段[]，故其内部整段都可以略去不写。

样例3

输入

a c { c | b { c e | d c } [ c b ] }

输出

a c
1 2

说明

末尾花括号{}代表必填段，其内含 $2$ 条岔路，逐层拆开后可见每条岔路都至少要写 $1$ 次关键字 $c$。于是整段写法里 $c$ 最少得写 $2$ 次。

样例4

输入

p q { u | v }

输出

p q
1 1

说明

尽管 {$u$|$v$} 表示 $u$ 与 $v$ 只能挑一个，合法语句既可以写成 $p$ $q$ $u$ ，也可以写成 $p$ $q$ $v$ 。

因此必填的就只剩 $p$ 与 $q$ 。

所谓必填关键字：指为了贴合该写法，正确语句里一定得出现的那些关键字。

样例5

输入

o { { f | { q | [ q | g | r ] | { g b w | e l h | a } } { l [ g l f | w l h | z ] { e | w g e | h } | { b k r | y | j } | g { w | e | l l i | i } { w g | y z q | a b y } | b { b | m | v } [ q | v l | k a ] } | [ { r a | f | r g e | f j } [ e f | i k g | y y | f a l ] { f k | y z | f f | o y b } | f { y o | b a w | f | b } [ m o | a w ] | [ h | o i ] ] | { { z f | i o r } { o k | v a q | e } [ o | v a ] | w [ e o q | b l ] | { r q | m | v y w } b l | [ v w | v w o | w g | m w ] [ j i | o | z ] } r e } [ { [ v e j | h k f | j ] | { f v | e e } | { b h e | r | j l g | v g } | { a | v } [ j i i | o q r | k ] } l { [ o | q | b j v | f o ] { w | l r b | w i } [ i k | l o w ] | [ v | i i g | l ] { a e | a w e | r } | [ a l | l | m f j ] o | [ v | g i m ] } | [ { o g f | f | v e j | m } | [ v o | r | y k k ] [ y y b | a z v | f q j | e w ] [ b | z e ] | { y j y | h q i | f i q } | { w m b | h | f w | k y } { e | m | z q | m } ] k [ b { h | e o e | g a z | i q f } | { v | g q | k o } g | { r q w | e | o | r } ] ] h | w { [ z | j { v z k | q | v a l | q q i } | [ o | b g b | k k ] [ e | r | o | e w v ] i ] [ { q | r | q v } [ y q y | b ] | { r | l m k | v i l } [ f v f | f v | l g w | a q ] w | y ] o | [ r g | [ y w q | o b | g e ] | { f | h e | w r r | k } [ a g | w m ] h ] { i | [ k k v | o y | z e l ] { h | m g | v v v | z } e } { [ i | f j i | i h ] | { w | v r | y q z } | [ b q h | b j | m i m | e r ] } | { [ k h | h | l w i | q r ] | [ m e j | g v ] [ h i k | j j l ] { v | k } } l } | k { { z | [ v q | o | a y ] { r e l | a i w } r } [ [ k i f | w | w m y | e ] [ j w h | k | z w l ] | { q q e | v a k | q f v | m f w } | [ a | a b h | a y k ] a ] | { r { f r r | g | w } | f f f } r | k } b | { [ { l | g z | g } [ j | h y b | r m | q h l ] { h q | y } | b ] { [ v f g | o | r | l q j ] | [ e z a | i v b | q g | k ] [ a | h | o | v z o ] } o | z [ { h i | e a } [ j k | e ] [ q r | m j ] | l [ m j | l e v ] ] { { f j | r v } | a v | { h g z | z o | e i | z } [ m o | j | l f z ] f | [ h k r | a q | z ] [ m g | l ] } } { { { o w o | z | z q } [ o m q | o m | b y r ] { r y b | g y k } | f v } b [ h { o | e i | r y e | o r } a | { b z a | k } { l | j | l l g } [ y | e o | b i y | w ] | { a f b | m q | g } j | { o j v | o k g } [ m f i | b m | q e | j ] z ] | r | [ { b h e | l | y q } [ w | q k | a ] | { h e q | j y | z r h | k } | h j [ y | f | w ] ] k } { e | { [ e | z | h | l g q ] [ h g | z ] | { m f e | l } | q b { i o l | e k g | g } | g k } } }

输出

o
1

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写