시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

어떤 수열이 주어졌을 때, 이 수열을 회전하면 여러 가지 수열을 얻을 수 있다. 이와 같이 수열을 회전하면서 얻은 수열들이 모두 원래의 수열보다 같거나 크면, 원래의 수열을 목걸이 수열이라 부른다. 예를 들어 01011은 목걸이 수열인데, 이는 10110, 01101, 11010, 10101, 01011 중에서 제일 작은 것이 원래의 01011이기 때문이다.

0과 1로 구성된 수열 S가 주어졌을 때, 이를 목걸이 수열들로 분해할 수 있다. 가장 간단한 방법은 각각의 숫자 단위로 분해하는 것인데, 그 외에도 다음의 조건을 만족하도록 분해할 수도 있다.

(1) 분해된 각각의 목걸이 수열들이 감소하는 순서대로 나타난다.

(2) 분해된 각각의 목걸이 수열들에 대해서, 인접한 두 개의 목걸이 수열을 붙였을 때 목걸이 수열을 이루지 않는다.

예를 들어 11101111011과 같은 수열이 있다고 했을 때, 이 수열은 (111)(01111)(011)로 분해할 수 있다. 이 경우 각각이 목걸이 수열임은 자명하고, 111 > 01111 > 011이 성립하며, 11101111과 011110111 중 어느 것도 목걸이 수열이 아니므로 위의 두 조건을 만족하는 예가 된다.


  0과 1로 이루어진 수열이 주어졌을 때, 위의 두 조건을 만족하도록 목걸이 수열들로 분해하는 방법을 찾아내는 프로그램을 작성하시오.

수열 사이의 대소 관계는 사전식 순서로 정의한다. 즉, A < B의 관계가 성립하는 경우는 A 뒤에 몇 글자를 붙이면 B가 되는 경우나, A와 B가 앞의 몇 개의 숫자가 같고 그 다음 숫자는 B에 있는 숫자가 더 큰 경우이다. 예를 들면 001 < 0010, 1101011 < 11011000이 성립한다. 이진수의 크기가 아님에 주의한다.

입력

첫째 0과 1로 이루어진 수열이 주어진다. 수열은 공백 없이 붙어서 주어지며, 그 길이는 1이상 100이하이다.

출력

첫재 줄에 목걸이 수열로 분해한 방법을 출력한다. 이를 위해서 각각의 목걸이 수열을 괄호로 묶어서 출력한다.

예제 입력

11101111011

예제 출력

(111)(01111)(011)

힌트