Decode an Encoded String

hard

Given a string encoded according to a specific pattern, decode it to retrieve the original message. The encoding pattern involves wrapping a repeated segment of the string in a prefix which indicates how many times the segment should occur. The repeated segment of the string is always enclosed within square brackets [ ]. More than one segment of the string can be encoded and nested encodings are possible.

Example 1

Input

[
  "3[a]"
]

Output

aaa

Explanation. The segment 'a' is repeated 3 times.

Example 2

Input

[
  "2[abc]3[cd]ef"
]

Output

abcabccdcdcdef

Explanation. The segment 'abc' is repeated 2 times and 'cd' is repeated 3 times. Then the characters 'ef' follows as they are.

Example 3

Input

[
  "3[a2[c]]"
]

Output

accaccacc

Explanation. The segment 'c' is repeated 2 times inside the repeating segment of 'a', and then 'a' along with its nested 'cc' is repeated 3 times.

Example 4

Input

[
  "2[b4[F]c]"
]

Output

bFFFFcbFFFFc

Explanation. The characters 'b' and 'c' encapsulate a repeated segment 'F' 4 times, and this complete pattern 'bFFFFc' itself repeats twice.

Follow-up: Can the algorithm be optimized to handle very deep nesting by using non-recursive techniques?

Constraints:

The input string will always be valid and non-empty, conforming to the given encoding pattern. The input string's length won't exceed 1000 characters.