Find the matching brackets
Given a string of opening and closing brackets, you are asked to find the matching opening bracket for each closing bracket. It’s guaranteed that the given sequence of brackets is valid.
Input
The input contains a single line
s (1 ≤ |s| ≤ ).Output
For each closing bracket, the program should print the index of its corresponding opening one. The indices should be separated by a space.
Examples
Input | Output |
(()()) | 2 4 1 |
((())) | 3 2 1 |
()()() | 1 3 5 |
Explanation
- (()())
Bracket | ( | ( | ) | ( | ) | ) |
Index | 1 | 2 | 3 | 4 | 5 | 6 |
Opening index | - | - | 2 | - | 4 | 1 |
- ((()))
Bracket | ( | ( | ( | ) | ) | ) |
Index | 1 | 2 | 3 | 4 | 5 | 6 |
Opening index | - | - | - | 3 | 2 | 1 |
- ()()()
Bracket | ( | ) | ( | ) | ( | ) |
Index | 1 | 2 | 3 | 4 | 5 | 6 |
Opening index | - | 1 | - | 3 | - | 5 |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 10 MB