부처

옛날 어느 먼 나라에서 정부가 서류 감축부를 세웠습니다. 이 부처는 역사상 가장 큰 부처가 되었고, 엄청나게 많은 공무원이 일하고 있었습니다. 그러나 조직 구조는 매우 단순했습니다. 장관은 직속 부하를 최대 세 명까지 두었고, 그 부하들도 각각 직속 부하를 최대 세 명까지 두었으며, 이런 식으로 계속 이어졌습니다.

이번에 새 장관이 취임했습니다. 젊고 영리하며 이상으로 가득 찬 그는 부처 이름값을 하기로 마음먹고 자기 발밑부터 살펴보았습니다. 그는 조직 계층 곳곳이 완전히 똑같은 모양을 하고 있음을 알아챘고, 모양이 같은 조직은 틀림없이 같은 일을 하고 있으리라 생각했습니다. 두 조직이 서로 같다면 그중 하나는 불필요하니 해체하여 그 안의 공무원을 모두 해고할 수 있습니다. 여러분이 할 일은 구조가 서로 다른 부서가 몇 개인지 세는 것입니다.

부처의 조직 구조가 주어집니다. 모든 공무원은 정확히 한 명의 상관을 두며, 직속 부하는 최대 세 명(0명일 수도 있음)까지 둡니다. 단 하나의 예외는 장관으로, 그에게는 상관이 없습니다(다만 부하는 여전히 최대 세 명입니다). 한 공무원의 부하들 사이에는 정해진 순서가 없습니다.

부서란 한 공무원과 그의 모든 부하, 그 부하들의 모든 부하, 이렇게 계속 이어지는 사람들 전체를 뜻합니다. 특별한 두 경우는 (장관이 이끄는) 부처 전체와, 부하가 없는 공무원 한 명으로 이루어진 1인 부서입니다.

부서의 깊이란, 그 부서에 속한 공무원들의 사슬 $x_1, x_2, \ldots, x_d$ 가운데 가장 긴 것의 길이 $d$입니다. 여기서 모든 $1 \le i < d$ 에 대해 $x_i$ 는 $x_{i+1}$ 의 상관이어야 합니다. 1인 부서의 깊이는 $1$ 입니다.

두 부서 $A$ 와 $B$ 가 같은 구조를 가진다는 것은, 두 부서의 공무원 사이에 일대일 대응이 존재하여, 임의의 두 공무원 $x$, $y$ 에 대해 $x$ 가 $y$ 의 상관인 것과 $x$ 에 대응된 공무원이 $y$ 에 대응된 공무원의 상관인 것이 서로 필요충분조건이 되는 경우를 말합니다. $A$ 와 $B$ 가 같은 구조라면 두 부서의 우두머리도 서로 대응되며, 두 부서는 깊이도 같고 공무원 수도 같습니다.

아래 그림에서 부서 $A$ 와 $B$ 는 같은 구조이고, 부서 $C$ 는 둘 모두와 다른 구조입니다:

부서 A	부서 B	부서 C

모든 깊이에 대해 구조가 서로 다른 부서의 개수를 구하세요. 즉, 부처 전체의 깊이를 $d$ 라 할 때, 각 $i$ 에 대해 깊이가 $i$ 이면서 서로 구조가 다른 부서의 개수 $n_i$ 로 이루어진 수열 $n_1, \ldots, n_d$ 를 출력하면 됩니다.

입력은 부처의 조직 구조를 다음 표기법으로 나타낸 한 줄입니다. 각 부서는 (x1...xk) 로 표현하며, 여기서 $0 \le k \le 3$ 은 우두머리의 부하 수이고 각 xi 는 부하 한 명이 이끄는 부서의 코드입니다. 따라서 1인 부서는 () 로 표현됩니다. 부처 전체는 최상위 부서(부처 전체)의 코드로 주어집니다.

부처에는 장관을 포함하여 최대 $1\,000\,000$ 명의 공무원이 있습니다.

부처의 깊이, 즉 장관이 이끄는 부서의 깊이를 $d$ 라 할 때 $d$ 줄을 출력합니다. $i$ 번째 줄에는 깊이가 $i$ 이면서 구조가 서로 다른 부서의 개수를 출력합니다.