Hide

Problem L
Loop Invariant

/problems/loopinvariant/file/statement/en/img-0001.png

A circular piece of parchment.

Luna, a historian, was exploring the archives of an old monastery when she stumbled on a mysterious scroll of parchment. On it were only two types of symbols: ‘(’ and ‘)’. Soon she noticed that the sequence of symbols satisfies an interesting property: It can be constructed by repeatedly inserting ‘()’ at some position into an initially empty sequence. Historians call such sequences balanced. Figure 1 gives an example of a balanced sequence.

$\includegraphics[width=0.55\textwidth ]{bracket}$

Figure 1: Sample Input 2 derived by successively inserting ‘()‘ into an initially empty sequence.

The chief librarian of the monastery recently told Luna that some of the more elitist monks in the region had a habit of writing on circular pieces of parchment. In their minds, anyone incapable of immediately telling where the text on such a scroll started was also unworthy of knowing its content. Consequently, Luna quickly inspected the edges of her parchment strip. And sure enough, the edges at the left and right end of the parchment strip fit together perfectly, indicating that the parchment once actually was circular. While holding the left and right edges together and looking at the now circular parchment, she wonders whether the balanced sequence starting at the tear is the only such sequence that could have resulted from tearing the parchment apart. After all, it makes little sense trying to decrypt a text when you do not even know where it starts.

Input

The input consists of:

One line with a balanced sequence $s$ ($2\leq |s|\leq 10^6$), the sequence on Luna’s strip of parchment.

Output

Output “no” if there is no way to obtain a different balanced sequence by cutting the circular sequence, otherwise give any such sequence.

Sample Input 1	Sample Output 1
(()())(()())	no

Sample Input 2	Sample Output 2
()(())()	(())()()

Problem LLoop Invariant

Input

Output

Problem L
Loop Invariant