대체 괄호 표기법

괄호 문자열이 균형 잡혀 있다는 것은 여는 괄호마다 그 뒤에 짝이 되는 닫는 괄호가 하나씩 대응한다는 뜻이다. 닫는 괄호는 아직 짝을 찾지 못한 여는 괄호 중 가장 최근에 나온 것과 짝을 이룬다.

대체 괄호 표기법을 다음과 같이 정의한다. 괄호 쌍 하나마다 "start,end:" 형태의 헤더가 하나씩 대응한다. start와 end는 원래 문자열이 아니라 새로 만드는 표기법 문자열 자체의 인덱스다. start는 그 헤더의 ':' 바로 다음 문자의 인덱스이고, end는 이 괄호 쌍이 품고 있는 마지막 괄호 쌍의 헤더가 끝난 바로 다음 인덱스다. 그래서 새 문자열에서 start부터 end 직전까지를 잘라내면 이 괄호 쌍 안에 들어 있는 모든 괄호 쌍을 기술하는 대체 괄호 표기법이 나온다. 빈 괄호 쌍은 안에 아무것도 없으므로 start와 end가 같다.

헤더는 원래 문자열에서 여는 괄호가 나오는 순서대로 늘어놓는다.

각 인덱스는 10진수로 적었을 때의 자릿수만큼 문자를 차지한다. 예를 들어 인덱스 42는 2글자를 차지한다. 새 문자열의 인덱스는 0부터 시작하고, 표기법에 등장하는 인덱스는 모두 새 문자열의 처음부터 센 절대 인덱스다.

괄호 문자열 (())를 보자. 이 문자열의 대체 괄호 표기법은 4,8:8,8:이다. 괄호 쌍은 바깥쪽 하나와 안쪽 하나로 모두 둘이다. 바깥쪽 여는 괄호가 먼저 나오므로 바깥쪽 헤더 4,8:이 안쪽 헤더 8,8:보다 앞에 온다. 바깥쪽 헤더가 인덱스 0부터 3까지를 차지하므로 start는 4이고, 안쪽 헤더가 인덱스 4부터 7까지를 차지하므로 바깥쪽 end는 8이다. 새 문자열에서 인덱스 4부터 8 직전까지를 잘라내면 8,8:이 나오고, 이것이 바깥쪽 괄호 쌍이 품고 있는 내용을 기술한다. 5,11:11,11:도 규칙을 만족하지만 우리가 원하는 것은 가장 짧은 표기이므로 답은 4,8:8,8:이다.

입력은 한 줄로 주어진다. 여는 괄호와 닫는 괄호로만 이루어진 문자열 s가 들어 있다. s의 길이는 2 이상 4,000 이하다. 공백은 없다. s는 균형 잡힌 괄호 문자열임이 보장된다.

s를 대체 괄호 표기법으로 나타낸 문자열을 한 줄에 출력한다. 나타내는 방법이 여러 가지라면 가장 짧은 것을 출력한다. 가장 짧은 표기는 유일하다.