Necklace Sequence

Time limit2sMemory limit128 MB

Summary

Decompose a binary string into a strictly decreasing sequence of Lyndon-like necklace factors where adjacent concatenations fail the necklace property.

Level: Medium6 of 10
Topics: String, Greedy, String matching
Solved: No attempts yet

Problem

A binary sequence can be rotated as if it were written on a circle. If a sequence is lexicographically no greater than every rotation of itself, including the original rotation, call it a necklace sequence. The sequence 01011 is a necklace sequence because it is the smallest among 10110, 01101, 11010, 10101, and 01011.

You are given a binary sequence S. Split S into necklace sequences so that both conditions below hold.

The necklace sequences appear from left to right in strictly decreasing lexicographic order.
Concatenating any two adjacent necklace sequences does not produce a necklace sequence.

Write a program that prints such a decomposition of the given sequence.

The order between two sequences is lexicographic. A < B if appending one or more characters to A makes B, or if the two sequences share a prefix and the first differing character is larger in B. Thus 001 < 0010 and 1101011 < 11011000. This is not a comparison of binary numeric values.

Input

The first line contains a binary sequence S with no spaces. The length of S is between 1 and 100, inclusive.

Output

Print one line containing a decomposition that satisfies the conditions. Wrap each necklace sequence in parentheses and print them consecutively.

Examples2

Example 1
Input
```
11101111011
```
Expected output
```
(111)(01111)(011)
```
Example 2
Input
```
0001
```
Expected output
```
(0001)
```