Decode a String

The encoding rule is k[text]: the text inside the square brackets is repeated exactly k times. Brackets can be nested. Return the decoded string.

For "3[a2[c]]" the answer is "accaccacc"; for "2[ab]3[c]" it is "ababccc".

Examples

Example 1

Input:

decode_string('3[a2[c]]')

Output:

'accaccacc'

Example 2

Input:

decode_string('2[ab]3[c]')

Output:

'ababccc'

Constraints

• 0 <= len(s) <= 2000
• s has lower-case letters, digits and brackets, and is always valid.
• k is a number from 1 to 300 and the decoded length is at most 200000.