Decode Nested Repeats

In this compact format, k[text] stands for text written k times, so "3[ab]" means "ababab". Brackets can be nested: in "2[a3[b]c]" the inner part 3[b] becomes "bbb" first, which gives "abbbcabbbc". Letters outside brackets stand for themselves.

Write decode(encoded) that returns the fully expanded string.

Examples

decode("3[ab]")      # returns 'ababab'
decode("2[a3[b]c]")  # returns 'abbbcabbbc'
decode("ab2[cd]ef")  # returns 'abcdcdef'

Constraints

• encoded has 0 to 1,000 characters and is always well formed: every number is followed by [, every [ comes right after a number, and the brackets are balanced.
• Repeat counts are whole numbers from 1 to 1,000, so they can have several digits.
• Letters are lowercase a-z, and the text inside brackets may be empty.
• The decoded string has at most 100,000 characters.