در کشور ناریا $n$ شهر وجود دارد. هر شهروند ناریا علاوه بر شماره شناسنامه دارای شماره قدرتی شناسنامه نیز هست. هم‌چنین هر شهر به شماره $(1 \leq i \leq n)$ دارای عدد امنیتی $v_i$ می‌باشد. اگر فرد $x$ بخواهد وارد شهر $i$ شود، باید شماره قدرتی شناسنامه $x$ بیشتر یا مساوی $v_i$ باشد. می‌دانیم تمام افرادی که در هر شهر $x$ زندگی می‌کنند دارای شماره قدرتی شناسنامه‌ای بیشتر یا مساوی $v_x$ هستند.
در این کشور همه دزدان به شدت قدرتمند هستند، به همین دلیل اگر یک دزد در شهر $x$ قرار داشته باشد می‌تواند شهر $x$ یا هر کدام از شهرهایی که با یک جاده مستقیم به شهر $x$ متصل هستند را غارت کند. توجه داشته باشید که دزد برای این کار لازم نیست به هیچ شهر دیگری نقل مکان کند!!!
اخیراً یک دزد $k$ شهر از این کشور را غارت کرده است. از آنجایی که هیچ اطلاعاتی در مورد این که کدام شهرها غارت شده‌اند نداریم، از شما می خواهیم به ازای هر $(1 \leq i \leq n)$ به‌دست آورید در صورتی که دزد در ابتدا در شهر $i$ام قرار داشته، حداقل شماره قدرتی شناسنامه او چقدر باید باشد تا بتواند با شروع از شهر $i$ام و حرکت بین شهرها و انجام دزدی در شهرهای مختلف حد اقل $k$ شهر را غارت کند.
توجه داشته باشید که یک دزد هر شهر را حداکثر یک بار می‌تواند غارت کند ولی می‌تواند به هر تعداد دلخواه از هر شهر یا جاده عبور کند.
در تنها سطر خروجی $n$ عدد چاپ کنید که عدد $i$ام برابر است با کمینه قدرت شناسنامه‌ای دزد در صورتی که اگر در ابتدا در شهر $i$ام قرار داشته باشد بتواند $k$ شهر را غارت کند.