در کشور ناریا $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$ شهر را غارت کند.

توجه داشته باشید که‌یک دزد هر شهر را حداکثر یک بار می‌تواند غارت کند ولی می‌تواند به هر تعداد دلخواه از هر شهر یا جاده عبور کند.

• در سطر اول ورودی سه عدد $(1 \leq n \leq 200000)$، $( 1 \leq m \leq 200000)$ و $(1 \leq k \leq n)$ به ترتیب نشان‌دهنده تعداد شهرها، تعداد جاده‌ها و تعداد شهرهای غارت شده آمده است.
• در سطر بعدی $n$ عدد $v_1$ تا $v_n$ به ترتیب آمده‌اند.
• $(1 \leq v_i \leq 1000000)$
• در $i$امین سطر از $m$ سطر بعدی در هر سطر دو عدد $(1 \leq a_i,b_i \leq n, a_i \neq b_i)$ آمده است که نشان‌دهنده‌یک جاده دو طرفه بین شهرهای $a_i$ و $b_i$ است. شهرها و جاده‌ها به گونه‌ای هستند که می‌توان از هر شهری به هر شهر دیگر از طریق جاده‌ها مسافرت کرد.

در تنها سطر خروجی $n$ عدد چاپ کنید که عدد $i$ام برابر است با کمینه قدرت شناسنامه‌ای دزد در صورتی که اگر در ابتدا در شهر $i$ام قرار داشته باشد بتواند $k$ شهر را غارت کند.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت