Однажды горилла нашла дерево на $n$ вершинах. Корнем этого дерева является вершина $1$, а на рёбрах этого дерева записаны веса. Любая порядочная горилла захотела бы залезть на такое дерево и эта не стала исключением. Обратите внимание, что в этой задаче корень дерева находится наверху.

Горилла может начать свой путь в любой вершине с номером $v$ ($2 \le v \le n$). Изначально её усталость равна $1$. Когда горилла поднимается по ребру наверх (ближе к корню), её усталость \textbf{умножается} на вес этого ребра.

Горилла имеет выносливость $k$, поэтому она откажется идти по ребру, после которого её усталость станет \textbf{строго больше} $k$ и \textbf{немедленно} закончит путешествие. Если такое ребро не встретилось, горилла закончит путешествие в корне.

Назовём \textit{продолжительностью} путешествия количество рёбер, по которым прошла горилла. Обозначим \textit{продолжительность} путешествия из вершины $v$ как $d_v$.

Помогите горилле узнать числа $d_2, d_3, \ldots, d_n$. Другими словами, найдите \textit{продолжительности} путешествия, если горилла будет начинать свой путь из вершины с номером $v$ ($2 \le v \le n$).
