题目内容

给定一个经过编码的字符串 $s$，请按照编码规则对字符串进行解码，并输出解码后的字符串。

编码规则为 $k[encoded_string]$，表示方括号内部的字符串 $encoded_string$ 需要连续重复 $k$ 次，其中 $k$ 为正整数。

编码可以嵌套。例如，$3[a2[c]]$ 表示将 $a2[c]$ 重复 $3$ 次，其中 $2[c]$ 又表示将字符 $c$ 重复 $2$ 次。

可以保证输入字符串始终是有效的，字符串中不存在多余的空格，并且所有方括号均符合格式要求。

原始字符串中不包含数字，字符串中出现的所有数字都只用于表示重复次数 $k$。因此不会出现 $3a$ 或 $2[4]$ 这样的输入。

测试数据保证解码后的字符串长度不会超过 $10^5$。

输入描述

输入一行字符串 $s$，表示经过编码的字符串。

约束

$1 \le |s| \le 30$

字符串 $s$ 由小写英文字母、数字以及方括号 $[$、$]$ 组成。

$s$ 保证是一个有效的编码字符串。

字符串中所有整数的取值范围为 $1$ 到 $300$。

解码后的字符串长度不超过 $10^5$。

输出描述

输出一行字符串，表示将字符串 $s$ 完全解码后的结果。

样例1

输入

3[a]2[bc]

输出

aaabcbc

说明

$3[a]$ 表示将字符串 $a$ 重复 $3$ 次，得到 $aaa$。

$2[bc]$ 表示将字符串 $bc$ 重复 $2$ 次，得到 $bcbc$。

因此最终解码结果为 $aaabcbc$。

样例2

输入

3[a2[c]]

输出

accaccacc

说明

首先对内部的 $2[c]$ 进行解码，得到 $cc$。

因此 $a2[c]$ 解码后为 $acc$。

再将 $acc$ 重复 $3$ 次，最终得到 $accaccacc$。

样例3

输入

2[abc]3[cd]ef

输出

abcabccdcdcdef

说明

$2[abc]$ 解码后得到 $abcabc$。

$3[cd]$ 解码后得到 $cdcdcd$。

最后再拼接字符串 $ef$，得到 $abcabccdcdcdef$。

样例4

输入

abc3[cd]xyz

输出

abccdcdcdxyz

说明

字符串 $abc$ 和 $xyz$ 不需要进行解码。

$3[cd]$ 表示将字符串 $cd$ 重复 $3$ 次，得到 $cdcdcd$。

因此最终解码结果为 $abccdcdcdxyz$。