Decode String

You are given an encoded string where the encoding rule is: \( k[encoded\_string] \), meaning the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer. The encoding can be nested, for example, 3[a2[c]] should be decoded as accaccacc.

Your task is to decode the given string and print its decoded result.

Constraints: The input string is non-empty and well-formed according to the rules described.

Hint: Use a stack to keep track of previous strings and repetition counts when encountering nested encodings.

inputFormat

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

Example:

3[a2[c]]

outputFormat

Output the decoded string to stdout.

For the above example, the output should be:

accaccacc

## sample

3[a]

aaa