کشور کرکس‌آباد از $n$ شهر تشکیل شده که توسط $n-1$ جاده به هم متصل شده‌اند، به طوری که با استفاده از این جاده‌ها می‌توان از هر شهری به هر شهر دیگری سفر کرد. فاصله دو شهر $x$ و $y$ در کرکس‌آباد، برابر تعداد جاده‌هایی است که برای رفتن از شهر $x$ به شهر $y$ باید از آنها عبور کرد.
امسال $$100امین سال تأسیس کشور کرکس‌آباد است و کرکس بزرگ (پادشاه کرکس‌آباد) دستور داده تا جشن بزرگی برگزار شود. مسئولیت مراسم آتش‌بازی را به ملکه‌ی کرکس‌آباد، شیکرکس سپرده است. طبق برنامه‌ریزی شیکرکس، مراسم آتش‌بازی در $ q $ شب برگزار می‌شود و آتش‌بازی شب $i$ام را شهر $v_i$ برگزار می‌کند. متأسفانه شیکرکس به جای خرید مواد آتش‌بازی مرغوب، مواد چینی خریداری کرده و این مواد دارای اشکال هستند، و زمانی که آتش‌بازی در شهر $x$ اجرا می‌شود، مراسم فقط در شهرهایی قابل مشاهده است که دقیقاً در فاصله $k$ از شهر $x$ قرار دارند.
کرکس بزرگ که از بی‌مسئولیتی شیکرکس عصبانی شده، به او دستور داده که سریعاً محاسبه کند هر شهر در چند شب می‌تواند مراسم آتش‌بازی را مشاهده کند. اما شیکرکس که با برنامه‌نویسی آشنایی ندارد، نمی‌تواند این کار را انجام دهد و برای همین از شما خواسته تا به او کمک کنید.
در تنها سطر خروجی باید $n$ عدد چاپ کنید که عدد $i$ام آن برابر با تعداد آتش‌بازی‌هایی است که در شهر $i$ام قابل مشاهده هستند.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 3 2 5 3 4 5 2 5 1 5 3 4 5 | 2 2 1 1 0 |
| 3 2 4 2 1 2 6 1 5 6 5 6 3 4 | 0 1 1 1 0 2 |