Given an encoded string, return its decoded string.
The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is being repeated exactly `k` times. Note that `k` is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc.
### Constraints
- `1 <= s.length <= 30`
- `s` consists of lowercase English letters, digits, and square brackets `'['` and `']'`.
- All the integers in `s` are in the range `[1, 300]`.
### Input Format
A single line containing the encoded string `s`.
### Output Format
Print the decoded string.
Sample Cases
Example 1Sample Case
Input: 3[a]2[bc]
Output: aaabcbc
Example 2Sample Case
Input: 3[a2[c]]
Output: accaccacc
Example 3Sample Case
Input: 3
Output:
Example 4Sample Case
Input: 3[
Output:
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.