+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- *دوست‌داران استاد مجتبی در انتظار بازگشت او از اردوی جهادی پیراهن می‌‌درند.* در فیاض‌کده $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) $$

حل سؤال در بانک سؤالات