1538: 简单的解压缩算法

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:4 Solved:4

Description

现需要实现一种算法,能将一组压缩字符串还原成原始字符串,还原规则如下:

1、字符后面加数字N,表示重复字符N次。例如:压缩内容为A3,表示原始字符串为AAA。

2、花括号中的字符串加数字N,表示花括号中的字符重复N次。例如压缩内容为{AB}3,表示原始字符串为ABABAB。

3、字符加N和花括号后面加N,支持任意的嵌套,包括互相嵌套,例如:压缩内容可以{A3B1{C}3}3

Input

输入一行压缩后的字符串

Output

输出压缩前的字符串

Sample Input Copy

{A3B1{C}3}3

Sample Output Copy

AAABCCCAAABCCCAAABCCC