题目描述

在命令格式定义字符串中，关键词（令牌）通过空格分隔，并有以下结构化标记：

• 大括号 { … } 表示“必选分支”，内部是若干以 | 分隔的分支，必须选择其中之一；
• 中括号 [ … ] 表示“可选分支”，内部内容可选出现；
• 分支内部又可嵌套任意深度的混合结构。

我们需要统计在任意合法命令中，每个必选关键词至少需要出现的次数。必选关键词指：无论如何选择可选分支或必选分支，都必须出现的那些关键词；其出现次数取每种最小分支组合下的最低值，再取所有分支的最大值（因为分支二选一，需对每条分支计算，然后取最小，再对并列大括号分组累加）。

题目内容

在 $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