Uniform Subtrees

Define a *Uniform* tree as one in which all of the
nodes at a given level (i.e. distance from the root) have the
same degree (i.e. number of children). Since all of the nodes
at a given level have the same number of children, a uniform
tree can be represented as simply a list of integers,
indicating the number of children at each level. For example,
the list `[2 3 5 0]` represents a tree
where the root has $2$
children, each child of the root has $3$ children, each grandchild has
$5$ children, and each
great-grandchild has no children, and is therefore a leaf.

For the purposes of this problem, redefine *Subtree*
as a connected subgraph of a tree that includes the tree’s
root. This is a bit different than the typical definition of
*Subtree*.

Given a description of a tree, find all of the unique
*Uniform Subtrees* of that tree. For example, here is a
tree and all of its unique uniform subtrees:

There will be a single test case in the input. Each test case will consist of a single tree, represented as a single string on one line. The string will be a sequence of matched opening and closing parentheses. Each matched pair represents a node, and the string between represents its children. There will not be more than $4\, 000$ nodes in the tree. There will be no whitespace, or any other characters, in the string.

Output every unique uniform subtree of the given tree as a list of integers, one subtree (and thus one list) per line. Print a single space between integers, and no spaces anywhere else. Do not print any blank lines between lists, or between test cases. Print the lists for a given test case sorted by the first element, then the second, then the third, and so on.

(Note: the first sample input & output case corresponds to the pictured tree and subtrees.)

Sample Input 1 | Sample Output 1 |
---|---|

(((()))(()(()())())) |
0 1 0 1 1 0 1 1 1 0 1 1 2 0 1 2 0 1 3 0 2 0 2 1 0 2 1 1 0 |

Sample Input 2 | Sample Output 2 |
---|---|

(()) |
0 1 0 |