Expand Repeat Notation

A compressed string uses the notation k[body], meaning body repeated exactly k times. Bodies may contain letters and further k[body] groups; k is a positive integer that may have several digits. Return the expanded string.

Examples

Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

Input:  s = "3[a2[c]]"
Output: "accaccacc"

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints

• 1 <= len(s) <= 100, s is well-formed
• The expanded string has at most 10**5 characters
• Target: O(length of output)

Goals

• Parse multi-digit numbers while scanning
• Save the outer context on a stack when entering a bracket and restore it on exit