시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB92222.222%

문제

Digion은 다음과 같이 정의한다.

  1. 빈 문자열도 Digion이다. 이것은 Null Digion이라고 부른다.
  2. '()'도 Digion이다. 이것은 기본 Digion라고 불리운다.
  3. AB가 Digion 일 때 (A)B도 또한 Digion이다. 이때 A를 안쪽의 Digion B를 바깥쪽의 Digion라고 부른다.

Digion의 무게는  '('와 ')' 쌍의 개수이다. 예를 들어, '()'의 무게는 1이다. 다음과 같은 값을 구하는 기준으로 Digion의 순서를 정의할 수 있다.

  1. 더 무거운 것이 더 비싸다.
  2. 만약 두 Digion의 무게가 같다면 안쪽 Digion가 비싼 것이 더 비싸다.
  3. 두 Digion의 무게가 같고 안쪽 Digion의 값까지 같다면 바깥쪽 Digion가 비싼 것이 더 비싸다.

위의 기준으로 값이 싼 것부터 비싼 것 순서로 정렬을 할 수 있다. Digion 하나가 주어질 때 그 Digion보다 바로 다음으로 비싼(정렬했을 때 바로 뒤에 올) Digion을 구해보자.

입력

첫째 줄에 Digion이 주어지며, 문자열의 끝은 '$'로 표시한다. 입력으로 주어지는 Digion의 무게는 30 이하이다.

출력

첫째 줄에 입력으로 주어진 Digion의 바로 다음으로 비싼 Digion을 출력한다.

예제 입력 1

()$

예제 출력 1

()()

예제 입력 2

()()$

예제 출력 2

(())

예제 입력 3

(()(()))(()())$

예제 출력 3

(()(()))((()))