Ministry

Long ago, in a faraway country, the government created the Ministry of Paperwork Reduction. It became the largest ministry ever, employing an enormous number of officials. Yet its structure was simple: the minister had at most three direct subordinates, each of those had at most three direct subordinates, and so on.

A new minister has just taken office. Young, sharp and full of ideals, he decided to live up to his ministry's name and start at home. He noticed that many parts of the hierarchy have exactly the same shape, and units with the same shape must be doing the same job. Whenever two units are identical, one of them is redundant and can be dissolved, laying off all of its officials. Your task is to count how many structurally different departments exist.

You are given the organizational structure of the ministry. Every official has exactly one superior and at most three direct subordinates (possibly zero). The only exception is the minister, who has no superior (but still at most three subordinates). The subordinates of an official are not ordered.

A department consists of an official together with all of their subordinates, all of their subordinates' subordinates, and so on. Two special cases are the full ministry (headed by the minister) and a one-man department, a single official with no subordinates.

The depth of a department is the length $d$ of the longest chain $x_1, x_2, \ldots, x_d$ of officials in the department such that $x_i$ is the superior of $x_{i+1}$ for every $1 \le i < d$. A one-man department has depth $1$.

Two departments $A$ and $B$ have the same structure if there is a one-to-one correspondence between their officials such that, for every pair of officials $x$ and $y$, $x$ is the superior of $y$ if and only if the official matched with $x$ is the superior of the official matched with $y$. If $A$ and $B$ have the same structure, then their heads correspond and they have the same depth and the same number of officials.

In the picture below, departments $A$ and $B$ have the same structure, while department $C$ is different from both:

Department A	Department B	Department C

Determine, for every depth, the number of structurally different departments. In other words, produce a sequence $n_1, \ldots, n_d$, where $d$ is the depth of the whole ministry and, for each $i$, $n_i$ is the number of departments of depth $i$ with pairwise different structures.

The input is a single line describing the structure of the ministry with the following notation. Each department is encoded as (x1...xk), where $0 \le k \le 3$ is the number of the head's subordinates and each xi is the code of one subordinate's department. A one-man department is therefore encoded as (). The whole ministry is given as the code of the full ministry.

The ministry contains at most $1\,000\,000$ officials (including the minister).

Output $d$ lines, where $d$ is the depth of the ministry, i.e. the depth of the department headed by the minister. The $i$-th line contains the number of departments of depth $i$ that have different structures.