题目内容

在 IP 网络运维体系中，对设备下发操作指令均需依赖特定的配置命令行。设备的产品说明文档会针对其支持的每一条命令，给出标准化的格式定义。为了准确解析这些命令格式，需遵循以下规范：

• 关键字（k）：在命令中必须原样输入且保持固定不变的部分。规定该部分仅由单个小写英文字母构成。
• 可选分组（[x]）：使用方括号 [] 包含的内容，表示在实际执行命令时该部分可以省略。
• 可选择一（[x | y]）：表示在多个候选项中选取其一，或者整体不予选取。
• 必选分组（{x}）：使用花括号 {} 包含的内容，表示在实际执行命令时该部分必须出现。
• 必选择一（{x | y}）：表示必须从多个候选项中严格选取一个。

补充约定：

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 ] }

现假设所有给定的命令格式定义均合法有效，且关键字、分支符及括号间均已按规范用空格分隔。给定一个命令格式定义字符串，请统计其中每个必选关键字至少需要出现的次数。

约束条件：

• 命令格式定义字符串的最大长度为 1000。

输入描述

输入为一个字符串，表示一条命令的格式定义。该定义保证格式正确，且关键字、分支符、括号之间均以空格分隔。无需考虑诸如 d k r { a|d} 等错误格式。

输出描述

输出共两行。 第一行按单词字母顺序输出所有的必选关键字，中间用一个空格隔开。 第二行对应第一行各个必选关键字的位置，输出其至少需要出现的最小次数，中间用一个空格隔开。

样例1

输入

a [ b | c ] d

输出

a d
1 1

说明

关键字 a 和 d 位于可选分组之外，无论可选分组是否选择，它们都会出现 1 次。

可选分组 [ b | c ] 可以整体不选，因此 b 和 c 的最小出现次数均为 0，不属于必选关键字。

所以必选关键字按字典序为 a d，对应最小出现次数为 1 1。

样例2

输入

a { x y | z x } b

输出

a b x
1 1 1

说明

关键字 a 和 b 位于必选分组之外，始终出现 1 次。

在必选分组 { x y | z x } 中，两个分支都包含关键字 x，且次数均为 1，因此 x 的最小出现次数为 1。

关键字 y 只在第一个分支出现，关键字 z 只在第二个分支出现，它们在另一个分支中的出现次数为 0，所以最小出现次数均为 0，不是必选关键字。

按字典序输出必选关键字为 a b x，对应最小出现次数为 1 1 1。

样例3

输入

{ a | b }

输出

说明

必选分组 { a | b } 必须选择其中一个分支。

选择第一个分支时，a 出现 1 次，b 出现 0 次；选择第二个分支时，b 出现 1 次，a 出现 0 次。

因此 a 和 b 的最小出现次数均为 0，不存在必选关键字，所以第一行和第二行均为空行。

样例4

输入

s y s t e m { i n t e r f a c e { g i g a b i t e t h e r n e t [ { 0 | 1 | 2 | 3 } ] | l o o p b a c k [ { 0 | 1 } ] } | r o u t e r { o s p f [ { p r o c e s s { 1 | 2 | 3 | 4 } } ] | b g p [ { a s { 1 0 0 | 2 0 0 | 3 0 0 } } ] | s t a t i c [ { d e f a u l t } ] } | v l a n { 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 0 } }

输出

e m s t y
1 1 2 1 1