Decode Encoded String

You are given an encoded string s where k[encoded_string] indicates that the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer. Your task is to decode the string.

The encoding rule is: k[encoded_string]. For example, the string "3[a]2[bc]" should be decoded as "aaabcbc".

You may assume that the input string is always valid; no extra white spaces, and well-formed square brackets. Furthermore, s does not contain any digits other than those used for the repeat numbers k.

inputFormat

The input consists of a single line containing the encoded string s.

Example: 3[a2[c]]

outputFormat

Output the decoded string corresponding to the input.

Example: accaccacc

3[a]2[bc]

aaabcbc