펜

Johnny는 질서를 좋아해서 엉망인 괄호를 보면 몹시 신경 쓴다. 최근 그는 문자열 ){([]를 보고 올바른 괄호 문자열이 아니라서 화가 났다. 다행히 주머니에 펜이 있어서 문자열 앞에 (를, 뒤에 )}를 추가할 수 있었다. 그러자 (){([])}가 올바른 괄호 문자열이 되어 그는 다시 편히 잘 수 있었다.

Johnny는 괄호 문자열을 고치는 일을 평생의 사명으로 삼았다. 문자열의 앞과 뒤에 새 괄호를 붙여서 올바르게 만든다. 펜의 잉크가 거의 떨어져 가므로, 붙이는 괄호 수를 최대한 적게 하려고 한다.

올바른 괄호 문자열은 다음과 같이 재귀적으로 정의한다.

• 빈 문자열은 올바른 괄호 문자열이다.
• S와 T가 올바른 괄호 문자열이면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다.
• S가 올바른 괄호 문자열이면 (S), [S], {S}도 올바른 괄호 문자열이다.

괄호 문자열을 입력받아 가장 짧은 수정 결과를 계산해 출력하거나, 수정할 수 없다고 알리는 프로그램을 작성하라.

첫 번째 줄에 비어 있지 않은 괄호 문자열이 주어진다. 문자열은 (, ), [, ], {, } 문자로만 이루어져 있으며, 길이는 최대 1,000,000이다. 이것이 Johnny가 고치려는 괄호 문자열이다.

입력 문자열을 고친 결과를 출력한다. 같은 최소 길이로 고칠 수 있는 방법이 여럿이면 그중 아무거나 출력해도 된다.

고칠 수 없으면 NIE를 출력한다.

첫 번째 예시는 문제 설명에 나온 것과 같다. 두 번째 예시에서는 이 문자열을 고칠 수 없다.