Uniform Subtrees

A uniform tree is a tree in which all nodes on the same level (depth from the root) have exactly the same number of children. Because each level has a single fixed number of children, a uniform tree can be described by an integer list giving the number of children at each level, from the root downward. The nodes on the last level have no children, so the list always ends with 0.

For example, [2 3 5 0] describes the uniform tree whose root (level 0) has 2 children, whose every level-1 node has 3 children, whose every level-2 node has 5 children, and whose level-3 nodes have no children.

A subtree always contains the root of the original tree. A uniform tree $[c_0, c_1, \dots, c_d]$ is a uniform subtree of the given tree if its nodes can be selected as follows: starting from the root, choose $c_0$ of its children, then from each chosen node choose $c_1$ of its children, and so on, so that at every level each chosen node actually has as many children as required. The subtree consisting of the root alone is written [0].

Given a tree, write a program that finds every distinct uniform subtree it has.

The input consists of several test cases. Each test case describes one tree as a string, given on its own line.

The string is made only of opening parentheses ( and closing parentheses ). A matching pair of parentheses represents one node, and the parenthesis pairs directly inside it represent that node's children. The whole string is wrapped in a single pair of parentheses that represents the root of the tree.

A single tree has at most 4,000 nodes, and the string contains no characters other than parentheses.

The last line of the input contains a single 0, which marks the end of the input.

For each test case, print the distinct uniform subtrees of the given tree, one per line.

Print each uniform subtree using the list representation described above, with a single space between the numbers of a list.

Within one test case, print the lists in lexicographic order, comparing the list elements as integers from left to right. Do not print a blank line between test cases.

The number of distinct uniform subtrees of a tree is exactly equal to the number of nodes in that tree; you can use this to sanity-check how many lines you print.