Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sofdor Ali and Bracket Sequence

Limits: 500ms, 512 MB

Sofdor Ali has invented a new game. He asked his assistant Jong Bahadur ( who happens to be a monkey ) to play the game.

Here is how the game is played:

  • Step 1: Sofdor Ali writes a sequence of brackets on a chalkboard.

  • Step 2: Jong Bahadur finds the lexicographically smallest regular bracket sequence ( if there is any ) that can be obtained by applying cyclic shift to the initial sequence.

Sofdor Ali and Jong Bahadur went on a vacation. But they left the bracket sequences behind so that we could play with them. For this task, we will give you the sequence of brackets written by Sofdor Ali and you have to tell us the sequence found by Jong Bahadur.

A regular sequence of brackets is defined as follows:

  • An empty string is a regular sequence of brackets.

  • If a string a is a regular sequence of brackets, then the string (a) is also a regular sequence of brackets.

  • If strings a and b are regular sequences of brackets, then the string ab is also a regular sequence of brackets. There are no other regular sequences of brackets.

Also notice that,

  • A string a is a cyclic shift of a string b if a and b have the same lengths and a consists of some (possibly empty) suffix from b followed by a prefix from b.

  • If a and b are two bracket sequences of the same length, a is lexicographically smaller than b if, for some i <= |a|, aj = bj for all j < i and ai = ‘(’, bi = ‘)’.

Input

The only line of input contains the sequence of brackets written by Sofdor Ali. The sequence is non-empty and its length doesn’t exceed 105.

For 30% of the cases, the length of the sequence will not exceed 103.

Output

Output the lexicographically smallest regular bracket sequence that can be obtained by applying cyclic shift to the initial sequence. If there is no such sequence, output ”-1” (without the quotation marks).

Samples

InputOutput
)()(()
(())()
((
-1

Explanation

For the first case, there were two possible cyclic shifts that obtained a regular sequence, ie: ()(()) and (())(). Among these two, (())() is lexicographically smaller.

For the second case, we have no cyclic shift that gets us a regular bracket sequence.

Author
  • Labib666's Avatar

    Labib666

    Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms.
Discussion