ParenthesesDiv1Easy

Correct parentheses sequences can be defined recursively as follows:

• The empty string "" is a correct sequence.
• If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
• If "X" is a correct sequence, then "(X)" is a correct sequence.
• Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".


You have a String s. You want to change it into a correct parentheses sequence.


You can only change the string using magic flips. In order to do a magic flip, you specify two 0-based indices L and R such that L <= R. The operation modifies the characters on indices from L to R, inclusive. First, the order of these characters is reversed. Then, each character is toggled to the opposite one. That is, each '(' in the specified range changes to a ')' and vice versa.


For example, suppose you have the string "((()". If you do a magic flip on the entire string (i.e., choosing L=0 and R=3), it first gets reversed to ")(((" and then all parentheses are toggled. Thus, flipping the string "((()" produces the string "()))".


Given s, find and report any sequence of at most 10 magic flips that changes s into a correct parentheses sequence. If there is no such sequence of magic flips, return the int[] {-1}. If there are multiple such sequences, you may return any of them. In particular, you are not required to find the shortest possible sequence of flips. The returned int[] should contain 2*F elements, where F is the number of flips you want to perform: for each flip, in order, first its L and then its R.