Loop Invariant

Interview

Time limit1sMemory limit1024 MB

Summary

Given a balanced parentheses string read as a circle, find a cyclic rotation that is balanced and differs from the original, or print no.

Level: Medium5 of 10
Topics: String, Prefix sum, String matching
Solved: No attempts yet

Problem

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 L.1 gives an example of a balanced sequence.

Figure L.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.

Examples2

Example 1
Input
```
(()())(()())
```
Expected output
```
no
```
Example 2
Input
```
()(())()
```
Expected output
```
(())()()
```