A9805 | And Yet Another Bracket Sequence

Polycarpus has a finite sequence of opening and closing brackets. In order not to fall asleep in a lecture, Polycarpus is having fun with his sequence. He is able to perform two operations:

- adding any bracket in any position (in the beginning, the end, or between any two existing brackets);
- cyclic shift — moving the last bracket from the end of the sequence to the beginning.

Polycarpus can apply any number of operations to his sequence and adding a cyclic shift in any order. As a result, he wants to get the correct bracket sequence of the minimum possible length. If there are several such sequences, Polycarpus is interested in the lexicographically smallest one. Help him find such a sequence.

Acorrect bracket sequence is a sequence of opening and closing brackets, from which you can get a correct arithmetic expression by adding characters "1" and "+" . Each opening bracket must correspond to a closed one. For example, the sequences "(())()", "()", "(()(()))" are correct and ")(", "(()" and "(()))(" are not.

The sequence $a_{1}$ $a_{2}...\ a_{n}$ is lexicographically smaller than sequence $b_{1}$ $b_{2}...\ b_{n}$ , if there is such number $i$ from $1$ to $n$ , that $a_{k}=b_{k}$ for $1<=k<i$ and $a_{i}<b_{i}$ . Consider that "(" $<$ ")".

The first line contains Polycarpus's sequence consisting of characters "(" and ")". The length of a line is from $1$ to $1000000$ .

Print a correct bracket sequence of the minimum length that Polycarpus can obtain by his operations. If there are multiple such sequences, print the lexicographically minimum one.