داوود و مشتلی برای تعطیلات به سواحل هاوایی رفتند و در طی عملیاتی مشتلی به داوود چندین هکتار از زمین‌های هاوایی را بدهکار شد. نقشه سواحل هاوایی به شکل یک درخت هست ولی هنوز دانشمندان اطلاعات دقیقی از شکلش به دست نیاورده‌اند. حالا مشتلی میخواهد از دست داوود فرار کند. از آنجا که این پول‌ها برای داوود عددی حساب نمی‌شود، فقط در صورتی از مشتلی پول‌ها را طلب می‌کند که فاصله‌اش از مشتلی کمتر از $d$ باشد. مشتلی که طلای المپیاد حسابداری دارد، به حساب و کتاب روی می‌آورد. مشتلی ارزش یک درخت را برابر تعداد راس‌هایی از درخت مثل $v$ تعریف می‌کند که اگر داوود در راس $v$ باشد ، مشتلی بتواند در راسی قرار بگیرد که فاصله‌اش از داوود بیشتر یا مساوی از $d$ باشد.

شایان از زمین‌شناسان معروف قرن $21$ است و در مورد سواحل هاوایی تحقیق می‌کند. او درختی $n$ راسی و ریشه‌دار که طبق معمول ریشه‌اش راس $1$ است را به مشتلی می‌دهد و میگوید نقشه سواحل هاوایی یکی از زیردرخت‌های این درخت است. حال مشتلی، درخت شایان و عدد $d$ را به شما ورودی می‌دهد و در قبال آن می‌خواهد به ازای هر راس مثل $v$، ارزش زیردرخت $v$ را به دست آورید.

در یک درخت ریشه‌دار، زیردرخت راس $v$ شامل تمام رئوس مانند $u$ است که در کوتاه‌ترین مسیر بین ریشه و $u$ راس $v$ ظاهر شده باشد.

در خط اول دو عدد $n$ و $d$ آمده است.

در خط بعدی $n-1$ عدد آمده است که در جایگاه $i$ ام پدر راس $i+1$ ام آمده است.

در یک خط $n$ عدد چاپ کنید که عدد $i$ ام ارزش زیردرخت راس $i$ است.

• ‌ زیرمسئله اول (۷ نمره): $n \le 300$
• زیرمسئله دوم ( ۱۲ نمره): $n \le 3000$
• زیرمسئله سوم (۱۷ نمره): ارتفاع درخت حداکثر 40 است.
• زیرمسئله چهارم (۴۳ نمره): $n \le 10^5$
• زیرمسئله پنجم (۲۱ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $2 \leq n \leq 3\times10^5$
• $1 \leq d \leq n$

• سوال بعد