+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
+ منبع: JOI 2014
----------
*دوست‌داران استاد مجتبی در انتظار بازگشت او از اردوی جهادی پیراهن می‌‌درند.*
در فیاض‌کده $n$ روستا با شماره‌های ۱ تا $n$ وجود دارد. از هر روستا دقیقا یک جاده‌ی خروجی دارد (دقت کنید که اگر از روستای $A$ بتوان به روستای $B$ رفت، نمی‌‌توان لزوما از روستای $B$ به $A$ نیز رفت، جاده‌ها یک‌طرفه اند).
استاد در کنار جویباری در روستای شماره 1 نشسته و گذر عمر می‌بیند. استاد که دلش هوای سفر کرده است می‌خواهد با شروع از روستای 1، $k$ جاده را بپیماید و در شهری که می‌رسد مستقر گردد. اهالی هر روستا می‌خواهند که استاد در روستای آنها مستقر گردد. ریش سفید فیاض‌کده می‌تواند یک شهر $p$ را انتخاب کند و جاده‌ی خروجی قبلی آنرا خراب کرده و سپس جاده ای از شهر $p$ به یک شهر $q$ دلخواه بکشد (این شهر $q$ می‌تواند همان شهر قبلی که $p$ به آن جاده داشت نیز باشد).
حال ریش سفید از شما کمک می‌خواهد که به ازای هر شهر $i$ به او بگویید چند زوج مرتب $(p,q)$ وجود دارد که استاد در نهایت در شهر $i$ مستقر گردد.
# ورودی
در خط اول دو عدد $n$ و $k$ آمده اند.
در خط $i$ام از $n$ خط بعدی عدد $U_{i}$ آمده که نشان دهنده شماره روستایی است که روستای $i$ ام به آن جاده دارد.
$$ 1 \le n \le 100\ 000 $$
$$ n \le k \le 10^{18} $$
# خروجی
در خط $i$ ام از $n$ خط خروجی جواب را به ازای شهر با شماره $i$ چاپ کنید.
# زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱| ۱۰ | $ n \le 100 $ |
|۲| ۳۷ | $ n \le 3\ 000 $ |
|۳| ۳۳ | $ U_{i} \neq U_{j}\ (1 \le i < j \le n) $ |
|۴| ۲۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
5 7
5
1
4
3
2
```
## خروجی نمونه ۱
```
1
2
3
3
16
```
جفت مرتب‌های درست به ازای هر $i$ عبارتند از :
$$1 : (1,1) $$
$$2 : (1,2), (2,2)$$
$$3 : (1,3), (2,3), (5,4)$$
$$4 : (1,4), (2,4), (5,3)$$
$$5 : (1,5), (2,1), (2,5), (3,1), (3,2), (3,3), (3,4), (3,5), (4,1), (4,2) (4,3), (4,4), (4,5), (5,1), (5,2), (5,5) $$