题目描述
批量命名工具支持花括号展开式：表达式由小写字母、,、{、} 组成。{A,B,…} 表示 从若干「替代项」中任选其一（替代项本身又可以是含花括号的表达式，即允许嵌套； 替代项允许为空），表达式其余部分按字面拼接。展开式的所有可能结果去重后按字典序 升序输出，每行一个；空结果输出一个空行。
输入格式
第一行一个整数 ；接下来 行，每行一个表达式（保证花括号配对合法， 保证展开结果数 且每个结果长度 100）。
输出格式
依次输出每个表达式的全部展开结果（去重升序）。
样例
输入
3
{a,b}c{d,e}
x{ab,}y
{p,p}q
输出
acd ace bcd bce xaby xy pq
数据范围
- 对于 30% 的数据，花括号不嵌套。
- 对于 60% 的数据，表达式长度 100。
- 对于 100% 的数据，1 1000，表达式长度 1000，所有表达式展开结果总数 ， 结果总长 ，高档数据中保证出现嵌套与重复结果。