정원 가꾸기

시간 제한1초메모리 제한2048 MB

요약

괄호 형식으로 주어진 트리에서 가장 왼쪽 잎부터 자를 때 노드가 잘리는 순서를 출력합니다.

문제

패션 공원 대회(FPC)를 준비하면서 마을 공원에 있는 나무를 모두 유행하는 모양으로 다듬으려 합니다. 할 일이 많아서 게임으로 만들기로 합니다. 모양이 특이한 나무를 하나 고르고, 모든 가지에 이름표를 붙인 뒤 다음 규칙에 따라 가지를 자릅니다.

나무는 문자열로 표현합니다. 각 노드에는 소문자 하나로 된 레이블이 붙어 있으며, 같은 레이블이 여러 노드에 있을 수 있습니다. 노드의 자식은 '('와 ')' 사이에 쉼표로 구분한 레이블 목록으로 적습니다. 잎, 즉 자식이 없는 노드 뒤에는 목록이 붙지 않습니다.

그림 G.1은 첫 번째 예제 입력의 나무를 나타냅니다. 이 나무에서는 레이블이 'b'인 잎을 가장 먼저 자르고, 다음으로 'd', 'e', 'f'를 자릅니다. 이제 'c'가 잎이 되므로 다음에 자릅니다. 마지막으로 'a'도 자를 수 있습니다.

나무의 부호화가 주어지면 이를 해석하고, 뿌리까지 모두 자른다고 할 때 노드를 자르는 순서를 구하세요.

첫 줄에 나무를 부호화한 문자열 $s$ ( $1\leq |s|\leq 10^5$ )가 주어집니다.

문자열에는 공백이 없으며, 어떤 나무를 올바르게 부호화한 것이라고 가정합니다.

나무에서 뿌리가 잘릴 때까지 노드를 자르는 순서대로 레이블을 이어 붙인 문자열을 출력합니다.