Digion

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

1. 빈 문자열은 Digion이다. 이를 Null Digion이라고 부른다.
2. ()는 Digion이다. 이를 기본 Digion이라고 부른다.
3. A와 B가 Digion이면 (A)B도 Digion이다. 이때 A를 안쪽 Digion, B를 바깥쪽 Digion이라고 부른다.

Digion의 무게는 (와 ) 쌍의 개수이다. 예를 들어 ()의 무게는 1이다. 다음 기준으로 Digion의 순서를 정할 수 있다.

1. 무게가 클수록 비싸다.
2. 두 Digion의 무게가 같으면 안쪽 Digion이 더 비싼 쪽이 더 비싸다.
3. 두 Digion의 무게가 같고 안쪽 Digion의 값도 같으면 바깥쪽 Digion이 더 비싼 쪽이 더 비싸다.

이 기준으로 싼 것부터 비싼 것 순서로 정렬할 수 있다. Digion 하나가 주어질 때, 그 Digion보다 바로 다음으로 비싼 Digion, 즉 정렬했을 때 바로 뒤에 오는 Digion을 구하자.

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

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