무작위 이진 탐색 트리

$N$개의 실수 키를 임의로 골라 트립(treap)에 삽입한다. 삽입이 끝난 뒤 트립의 높이가 $h$가 될 확률을 구하시오 ($h = 0, 1, \ldots, N-1$).

트립은 무작위 이진 탐색 트리이다. 각 노드는 키와 우선순위를 가지며, 두 값은 모두 0 이상 1 이하의 실수이다. 트립은 항상 다음 두 조건을 만족한다.

1. 키 조건: 각 노드의 키는 왼쪽 자식과 그 자손들의 모든 키보다 크고, 오른쪽 자식과 그 자손들의 모든 키보다 작다.
2. 우선순위 조건: 각 노드의 우선순위는 자식들의 우선순위보다 크다.

키가 $x$인 노드를 삽입하려면 다음 과정을 따른다.

1. 새 노드의 우선순위 $p$를 0 이상 1 이하에서 균등하게 무작위로 정한다.
2. 우선순위는 무시하고, 일반 이진 탐색 트리와 같은 방식으로 삽입한다.
3. 우선순위 조건이 깨지는 동안 회전하여 새 노드를 위로 올린다.

아래 그림은 위의 트립에 키 0.5, 우선순위 0.5인 노드를 삽입하는 과정이다.

0 이상 1 이하에서 균등하게 무작위로 $N$개의 키를 골라 빈 트립에 하나씩 삽입한다. 각 $h = 0, 1, \ldots, N-1$에 대해, 최종 트립의 높이가 $h$가 될 확률을 출력하시오. 실수는 충분히 정밀하게 다루며, 두 난수가 같을 확률은 0이다. 높이는 잎에서 루트까지 이동할 때 지나는 간선 수의 최댓값이다.

정수 $N$ ($1 \le N \le 3 \cdot 10^4$)이 주어진다.

$N$개의 줄을 출력한다. $i$번째 줄에는 높이가 $i-1$이 될 확률을 출력한다. 절대 오차는 $10^{-5}$ 이하여야 한다.