题目描述

在 IP 领域中对设备的操作是通过配置命令行实现，在设备的产品文档中会为该设备支持的每个命令定义格式。命令格式定义必须遵循格式定义的规范要求，规范要求如下表所示。 备注说明：

1.关键字、分组括号、分支选择符之间通过一个空格隔开。除了括号和分支选择符 ∣ 外，其他都视为关键字

2.命令行最长 1000 个字符长度。

下面是一些正确命令格式定义示例： 1.d r { k | n k } 2.d r [ { k | n k } ] 3.d k { k | r { k m | n k } [ k r ] } 假设产品文档中的命令格式定义都经过确认是正确的，并且关键字、分支符、括号之间都已经用空格隔开了。现在需要统计某个定义中每个必选关键字至少需要出现的次数。

输入描述

输入字符串为一个命令的格式定义，命令格式定义都经过确认是正确的，并且关键字、分支符，括号之间都已经用空格隔开了。暂不需要考虑错误格式比如这种 d k r {a∣d}。

输出描述

输出为两行，第一行为必选关键字，按单词字母顺序排序，并用一个空格隔开，第二行为对应第一行位置上必选关键字的最小出现次数，也是用一个空格隔开。

样例1

d r { k | n k }

d k r
1 1 1

说明

大括号分组{}表示必选，分组里面有 2 个分支，每个分支都有 k ，因此 k 是必须输入的，并且次数为 1 。

样例2

d r [ { k | n k } ]

d r
1 1

说明

后面的中括号是分组[]表示可选，因此里面的所有内容都可以不输入。

样例3

d k { k | r { k m | n k } [ k r ] }

d k
1 2

说明

后面的大括号分组{}表示必选，其中有 2 个分支，递归分析每个分支中都必须输入至少 1 个关键字 k 。因此整个表达式要输入的 k 的数量至少为 2 。

样例4

d r { m | n }

d r
1 1

说明

虽然，{m|n} 表示 m 和 n 二选一，合法命令可以输入 d r m 或者 d r n 。 所以必选关键就只有 d 和 r 。 必选关键字的意思是：要满足格式定义，正确命令中必须出现的关键字。

样例5

n { h { a i n | n [ v ] } | s i {m | k | m n } n | r i { { n | a } | m n } | g n | u n [ d n ] } { b { c | m n } } { c { d [ e ] f { c [ d ] { c { f { d e { a { b n } } } [ d ] } } } } } [ b ] n { h { b i n | n [ v ] } | s i { m | k | w w } n | r i { n | m n } | g n | u n [ d n ] | u { n | a } [ d n ] } { b { b | m n } } { c { d [ e ] f { d [ d ] { e { f { d [ d ] { e { f { d e { a { b n } } } [ d ] } } } } } { h { b i { n | a } | n [ v ] } | s i { m | k | w w } n | r i { n | m n } | g n | u n | [ d n ] | u n [ d n ] } { b { b | m n } } { c { d [ e ] f { d [ d ] { n { f { a { a { b n } } } [ d ] } } } } } [ x ] { n | a } { h { a i n | n [ v ] } | r i { n | m n } | g n | u n [ d n ] | u n [ d n ] } { b { b | m n } } { c { d [ e ] f { d [ d ] { e { f { d e { b { b n } } } [ d ] } } } } } [ k ] { n | a } { h { a i n | n [ v ] } | s i { m | k | w w} n | r i { n | m n } | g { n | a } | u { n | a } [ d n ] | u n [ d n ] } { n | [ d ] n } { [ a b ] | [ b n ] }

a b c d e f n
4 9 6 10 5 8 9