중첩 깊이

요약: 숫자로 이루어진 문자열 S가 주어질 때, 결과 문자열이 균형 잡힌 문자열이고 각 숫자 d가 정확히 d쌍의 서로 짝이 맞는 괄호 안에 있도록 여는 괄호와 닫는 괄호를 최소 개수만큼 삽입하라.

문자열에서 두 괄호의 중첩 영역은 그 두 괄호 사이에 엄격히 위치하는 부분 문자열이다. 여는 괄호와 그보다 오른쪽에 있는 닫는 괄호는, 두 괄호의 중첩 영역이 비어 있거나 그 중첩 영역에 있는 모든 괄호가 같은 중첩 영역의 다른 괄호와 짝이 맞으면 서로 짝이 맞는다고 한다. 위치 p의 중첩 깊이는 p가 m의 중첩 영역에 포함되는, 서로 짝이 맞는 괄호 쌍 m의 수이다.

예를 들어 다음 문자열에서는 모든 숫자가 자신의 중첩 깊이와 일치한다: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). 처음 세 문자열은 같은 숫자들이 같은 순서로 나타나는 문자열 중 길이가 최소이지만, 마지막 문자열은 그렇지 않다. ((22)1)에도 숫자 221가 있으며 길이가 더 짧기 때문이다.

숫자로 이루어진 문자열 S가 주어질 때, 다음 조건을 만족하며 괄호와 숫자로 구성된 또 다른 문자열 S'을 구하라.

• S'의 모든 괄호는 다른 어떤 괄호와 짝이 맞는다.

• S'에서 모든 괄호를 제거한 결과는 S이다.

• S'의 각 숫자는 자신의 중첩 깊이와 같다.

• S'의 길이는 최소이다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ S의 길이 ≤ 100.

테스트 세트 1 (공개 판정)

S의 각 문자는 0 또는 1이다.

테스트 세트 2 (공개 판정)

S의 각 문자는 0 이상 9 이하의 십진 숫자이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄은 하나의 테스트 케이스를 나타내며 문자열 S만을 담고 있다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 정의한 문자열 S'이다.

문자열 ()0000(), (1)0(((()))1), (1)(11)000은 각각 예제 케이스 #1, #2, #3의 올바른 답이 아닌데, 그 이유는 오직 길이가 최소가 아니기 때문이다. 또한 1)(와 )(1는 짝이 맞지 않는 괄호를 포함하고 있으며 1가 있는 위치에서 중첩 깊이가 0이므로 예제 케이스 #4의 올바른 답이 아니다.

문제 설명에서 언급한 예시 문자열에서 괄호를 제거하면 테스트 세트 2에만 유효한 예제 입력을 만들 수 있다.