CF524F.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 "("  <  ")".

Polycarpus 有一个由左括号和右括号组成的有限序列。为了在听课时不睡着，Polycarpus 正在用这个序列玩耍。他可以执行以下两种操作：

• 在任意位置（开头、结尾或任意两个现有括号之间）插入任意一个括号；
• 循环移位——将序列末尾的括号移到开头。

Polycarpus 可以对其序列执行任意次数的上述操作，且操作顺序任意。最终，他希望得到一个长度最小的合法括号序列。若存在多个满足条件的序列，则他希望得到其中字典序最小的一个。请帮助他找到这样的序列。

一个合法括号序列是指：通过在其中添加字符 "1" 和 "+"，可将其变为一个合法的算术表达式；并且每个左括号都必须有唯一对应的右括号与之匹配。例如，序列 "(())()"、"()"、"(()(()))" 是合法的，而 ")("、"(()" 和 "(())(" 则不是。

序列 $a_1 a_2 \dots a_n$ 在字典序上小于序列 $b_1 b_2 \dots b_n$，当且仅当存在某个下标 $i$（$1 \le i \le n$），使得对所有 $1 \le k < i$ 都有 $a_k = b_k$，且 $a_i < b_i$。规定 "("  <  ")"。

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

第一行包含 Polycarpus 的序列，该序列由字符 ( 和 ) 组成。行的长度为 $1$ 到 $1\,000\,000$。

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.

输出 Polycarpus 通过其操作能得到的最短长度的合法括号序列。如果存在多个满足条件的序列，则输出其中字典序最小的一个。

The sequence in the first example is already correct, but to get the lexicographically minimum answer, you need to perform four cyclic shift operations. In the second example you need to add a closing parenthesis between the second and third brackets and make a cyclic shift. You can first make the shift, and then add the bracket at the end.

第一个示例中的序列已经正确，但为了得到字典序最小的答案，你需要执行四次循环移位操作。在第二个示例中，你需要在第二个和第三个括号之间添加一个右括号，并进行一次循环移位。你可以先执行移位操作，再在末尾添加该括号。