유니폼 서브트리

유니폼 트리(uniform tree)는 같은 레벨(루트로부터의 깊이)에 있는 모든 노드가 똑같은 개수의 자식을 갖는 트리이다. 레벨마다 자식 수가 하나로 정해지므로, 유니폼 트리는 각 레벨의 자식 수를 루트부터 순서대로 나열한 정수 리스트로 나타낼 수 있다. 마지막 레벨의 노드는 자식이 없으므로 리스트는 항상 0 으로 끝난다.

예를 들어 [2 3 5 0] 은 루트(레벨 0)의 자식이 2개, 레벨 1의 각 노드의 자식이 3개, 레벨 2의 각 노드의 자식이 5개, 레벨 3의 노드는 자식이 없는 유니폼 트리를 나타낸다.

서브트리는 항상 원래 트리의 루트를 포함한다. 어떤 유니폼 트리 $[c_0, c_1, \dots, c_d]$ 가 주어진 트리의 유니폼 서브트리가 되려면, 루트에서 시작하여 루트의 자식 중 $c_0$ 개를 고르고, 고른 각 노드에서 다시 자식 $c_1$ 개를 고르는 식으로, 매 레벨에서 고른 모든 노드가 필요한 수만큼의 자식을 실제로 갖도록 노드를 선택할 수 있어야 한다. 노드 하나만으로 이루어진 서브트리는 [0] 으로 나타낸다.

트리가 주어졌을 때, 그 트리가 가질 수 있는 서로 다른 유니폼 서브트리를 모두 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 트리 하나를 나타내는 문자열이며, 한 줄에 하나씩 주어진다.

문자열은 여는 괄호 ( 와 닫는 괄호 ) 로만 이루어진다. 서로 대응하는 한 쌍의 괄호는 노드 하나를 나타내고, 그 괄호 안에 바로 들어 있는 괄호 쌍들이 그 노드의 자식을 나타낸다. 문자열 전체는 트리의 루트를 나타내는 하나의 괄호 쌍으로 감싸여 있다.

한 트리의 노드 개수는 4,000개를 넘지 않으며, 문자열에는 괄호 외의 다른 문자가 없다.

입력의 마지막 줄에는 0 이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다, 주어진 트리의 서로 다른 유니폼 서브트리를 한 줄에 하나씩 출력한다.

각 유니폼 서브트리는 문제에서 설명한 리스트 표현으로 출력하며, 리스트의 숫자 사이에는 공백을 한 칸 둔다.

한 테스트 케이스 안에서 리스트는 사전순으로 출력한다. 이때 사전순 비교는 리스트의 원소를 앞에서부터 정수로 비교한다. 테스트 케이스 사이에는 빈 줄을 넣지 않는다.

한 트리가 갖는 서로 다른 유니폼 서브트리의 개수는 그 트리의 노드 개수와 정확히 같다. 이 성질을 이용해 출력하는 줄 수를 검산할 수 있다.