• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• منبع: 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$ چاپ کنید.

زیرمسئله‎ها

مثال

ورودی نمونه ۱

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)$$