Algorithms and Data Structures

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

  1. (()())
      2. Bracket
      (
      (
      )
      (
      )
      )
      Index
      1
      2
      3
      4
      5
      6
      Opening index
      -
      -
      2
      -
      4
      1
  1. ((()))
      2. Bracket
      (
      (
      (
      )
      )
      )
      Index
      1
      2
      3
      4
      5
      6
      Opening index
      -
      -
      -
      3
      2
      1
  1. ()()()
      2. Bracket
      (
      )
      (
      )
      (
      )
      Index
      1
      2
      3
      4
      5
      6
      Opening index
      -
      1
      -
      3
      -
      5
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue