DIY: Decoding a String

Problem statement

Given an encoded string, return its decoded string.

The input string is encoded such that k[pattern] should be decoded to pattern repeatedly for k times. Note that pattern itself may include nested repetition encoding. For example, 3[a2[b]] represents abbabbabb.

k is guaranteed to be a positive integer. Furthermore, the string does not contain any digits, and any digit in the encoded_string only represents k.

Input

The input will be in the form of a string. The following is an example input:

s = "abc3[cd]xyz"

Output

The output will also be in the form of a string, and it will be the decoded version of the input string. The following is an example output for the above list:

Output: "abccdcdcdxyz"