POLSKI SPOJ

Masz dane drzewo zawierające n wierzchołków. Odległość między dwoma wierzchołkami to minimalna liczba krawędzi po których trzeba przejść, żeby dojść z jednego wierzchołka do drugiego. W szczególności odległość od wierzchołka do niego samego jest równa 0.

Zdefinijmy funkcję gęstości G(v, r) dla wierzchołka v oraz całkowitej nieujemnej liczby r. Niech ilość wierzchołków (z v włącznie) odległych od v o nie więcej niż r będzie równa m. Wtedy funkcja G(v, r) = m / (r + 1)².

Dla każdego wierzchołka v znajdź takie r, że G(v, r) jest największe możliwe. Jeśli istnieje wiele poprawnych r, to wypisz to największe.

Wejście

W pierwszym wejściu masz daną liczbę wierzchołków n. (2 ≤ n ≤ 10⁵).

Drzewo znajdujące się na wejściu jest ukorzenione w wierzchołku o indeksie 1. Na wejściu znajduje się n - 1 liczb. i'ta liczba a_i przedstawia indeks wierzchołka będącego ojcem wierzchołka o indeksie i + 1 (1 ≤ a_i ≤ i).

Wyjście

Wypisz n liczb. i'ta liczba oznacza najlepsze r dla wierzchołka o indeksie i.

Przykład

Wejście:
11

1 2 2 4 4 4 4 6 9 1

Wyjście:
0 2 0 1 0 0 0 0 0 0 0